home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / ADVTUT.MS < prev    next >
Text File  |  1992-12-08  |  81KB  |  2,692 lines
  1. .de iH
  2. \\$1 \\$2 \\$3 \\$4 \\$5 \\$6 \\$7 \\$8
  3. \\.XS
  4. .if \\n(NS-4     
  5. .if \\n(NS-3     
  6. .if \\n(NS-2     
  7. .if \\n(NS-1     
  8. \\*(SN \\$1 \\$2 \\$3 \\$4 \\$5 \\$6 \\$7 \\$8
  9. \\.XE
  10. ..
  11. .de 1s
  12. .nr PS 11
  13. .nr VS 12
  14. .br
  15. .LP
  16. ..
  17. .de 2s
  18. .nr PS 11
  19. .nr VS 16
  20. .br
  21. .LP
  22. ..
  23. .de cB
  24. .nr PS 9
  25. .nr VS 11
  26. .br
  27. .LP
  28. .KS
  29. .LD
  30. .ft CW
  31. ..
  32. .de cE
  33. .DE
  34. .KE
  35. .2s
  36. .ft R
  37. ..
  38. .EH 'PCCTS Advanced Tutorial 1.0x'
  39. .OH 'PCCTS Advanced Tutorial 1.0x'
  40. .EF '''Page %'
  41. .OF '''Page %'
  42. .TL
  43. \s+4PCCTS Version 1.0x Advanced Tutorial\s-4
  44. .AU
  45. Terence Parr, Hank Dietz, Will Cohen
  46. .AI
  47. School of Electrical Engineering
  48. Purdue University
  49. West Lafayette, IN  47907
  50. \fISpring 1992\fP
  51. \f(CWparrt@ecn.purdue.edu\fP
  52. \f(CWhankd@ecn.purdue.edu\fP
  53. \f(CWcohenw@ecn.purdue.edu\fP
  54. .2s
  55. .LP
  56. .br
  57. .PP
  58. Constructing a translator can be viewed as an iterative refinement
  59. process moving from language recognition to intermediate-form
  60. transformation.  This document presents one possible sequence of
  61. refinements.  We shall use as many features of PCCTS as is reasonable
  62. without regards to optimality.
  63. .PP
  64. We will develop a compiler for a simple string manipulation language
  65. called \fIsc\fP.  The compiler will generate code for a simple stack
  66. machine.
  67. .PP
  68. This document assumes familiarity with the concept of a parser generator and
  69. other language recognition tools \(em in particular, a passing familiarity
  70. with YACC is useful.
  71. .PP
  72. The development will proceed as follows:
  73. .IP \fI(i)\fP
  74. Define a grammar to recognize functions, statements, variable
  75. definitions and expressions in \fIsc\fP.
  76. .IP \fI(ii)\fP
  77. Add symbol table management to the grammar developed in \fI(i)\fP
  78. .IP \fI(iii)\fP
  79. Add actions to translate \fIsc\fP into stack code for a simple stack
  80. machine.
  81. .IP \fI(iv)\fP
  82. Construct trees as an intermediate-form.
  83. .IP \fI(v)\fP
  84. Build a code-generator to translate the trees into executable C code.
  85. .bp
  86. .NH
  87. .iH \fIsc\fP Language definition
  88. .PP
  89. \fIsc\fP is a simple, C-like language with only one data object
  90. type\(em string.  It has global variables, functions, arguments and
  91. local variables.  There are no arrays or structures.
  92. .NH 2
  93. .iH \fIsc\fP Expressions
  94. .PP
  95. Expression atoms are limited to variables, string constants
  96. (\f(CW"\fIcharacter(s)\f(CW"\fR) and function calls
  97. (\f(CWfunction(\fIexpr\f(CW)\fR).  The string constants
  98. \f(CW"false"\fP or \f(CW"0"\fP represent false and \f(CWtrue\fR or
  99. \f(CW"1"\fP represent true.  A limited set of operators are available
  100. (from highest to lowest precedence)
  101. .IP \f(CW-\fP 8n
  102. Unary operator negate. Numeric operator.
  103. .IP "\f(CW*, /\fP"
  104. Binary operators multiply and divide.  Groups left-to-right.  Numeric
  105. operator.
  106. .IP "\f(CW+, -\fP"
  107. Binary operators add and subtract.  Groups left-to-right.  Numeric
  108. operator except for \f(CW+\fP which is \*Qconcatenate\*U if one of
  109. operands is non-numeric.
  110. .IP "\f(CW==, !=\fP"
  111. Binary operators equal, not equal.  Groups left-to-right.  Numeric or
  112. non-numeric.
  113. .IP \f(CW=\fP
  114. Binary assignment operator.  Groups right-to-left.  For example,
  115. \f(CWa\ =\ b\ =\ c\fP means to assign \f(CWc\fP to \f(CWb\fP and then to
  116. \f(CWa\fP.
  117. .LP
  118. .NH 2
  119. .iH \fIsc\fP Functions and statements
  120. .PP
  121. Functions may have multiple local variables, but at most one parameter.
  122. All functions implicitly return a string to the
  123. calling function, although the value need not be used.  If a
  124. \f(CWreturn\fP-statement is not executed within a function, the return
  125. value for that function is undefined.  Functions are defined exactly
  126. as in C:
  127. .cB
  128. \fIfunction\fP(\fIarg\fP)
  129. {
  130.     \fIstatement(s)\fP
  131. }
  132. .cE
  133. .PP
  134. A function called \f(CWmain()\fP must exist so that our interpreter
  135. and compiled code knows where to begin execution.  Also, \f(CWmain()\fP
  136. always has a implicitly passed parameter which contains any
  137. command-line argument.
  138. .PP
  139. \fIsc\fP has six statements.
  140. .IP \f(CWif\fP
  141. Conditionals have the form:
  142. .RS
  143. .cB
  144. if ( \fIexpr\fP ) \fIstatement\fP
  145. .cE
  146. .RE
  147. .IP \f(CWwhile\fP
  148. Loops have the form:
  149. .RS
  150. .cB
  151. while ( \fIexpr\fP ) \fIstatement\fP
  152. .cE
  153. .RE
  154. .IP "\f(CW{\fP \fIstatement(s)\fP \f(CW}\fP"
  155. Block statements treat more than one statement as a single statement as
  156. in C.  However, one cannot define variables local to a block statement.
  157. .IP "\fIexpr\fP\f(CW;\fP"
  158. An \fIexpr\fP can include any valid \fIsc\fP expression, but only expressions
  159. involving assignments and function calls are useful.
  160. .IP "\f(CWreturn\fP \fIexpr\fP \f(CW;\fP"
  161. This statement behaves exactly like the C return statement except that
  162. only strings can be returned.
  163. .IP "\f(CWprint\fP \fIexpr\fP\f(CW;\fP"
  164. Print the string described by \fIexpr\fP to \f(CWstdout\fP.
  165. .NH 2
  166. .iH Example
  167. .PP
  168. The following code is a simple \fIsc\fP program that computes \fIn\fP
  169. factorial.
  170. .cB
  171. main(n)
  172. {
  173.     print fact(n);
  174.     print "\en";
  175. }
  176.  
  177. fact(n)
  178. {
  179.     if ( n == "0" ) return "1";
  180.     return n * fact(n - "1");
  181. }
  182. .cE
  183. .NH
  184. .iH Language recognition
  185. .PP
  186. We begin our project by constructing a parser\(ema program that will
  187. recognize phrases in \fIsc\fP.  The first two subsections describe the
  188. \fIsc\fP lexicon while the later subsections present the \fIsc\fP grammar
  189. with and without symbol table management.
  190. .NH 2
  191. .iH Lexical analysis
  192. .PP
  193. Our language has only strings of upper- and lower-case letters, called
  194. \f(CWWORD\fP's, operators, string constants and a few grammatical
  195. grouping symbols; all of which except \f(CWWORD\fP will be defined
  196. implicitly by mentioning them in the grammar.  \f(CWWORD\fP will be
  197. placed last in the grammar\(emi.e. after all keywords have been
  198. defined.  Since keywords are really just strings of characters as
  199. well, they must be treated specially.  When two (or more) regular
  200. expressions can be matched for the current input text, DLG scanners
  201. resolve the ambiguity by matching the input to the expression
  202. mentioned first in the description.  Hence, we place
  203. .cB
  204. #token WORD "[a-zA-Z]+"
  205. .cE
  206. .LP
  207. at the bottom of the file.
  208. .PP
  209. Tabs, blanks and carriage-returns are all considered white space and
  210. are to be ignored (although we wish to track line numbers).  The
  211. following ANTLR code will instruct the parser to skip over white space.
  212. .cB
  213. #token "[\et\e ]+"   << zzskip(); >>         /* Ignore White */
  214. #token "\en"        << zzline++; zzskip(); >>
  215. .cE
  216. .PP
  217. Strings are strings of characters enclosed in double-quotes.  For simplicity
  218. we will allow any character not in the ASCII range 0..0x1F (hex) plus
  219. any "escaped" version of the same character set.
  220. .cB
  221. #token STRING       "\e"(~[\e0-\e0x1f\e"\e\e]|(\e\e~[\e0-\e0x1f]))*\e"" <<;>>
  222. .cE
  223. .NH 2
  224. .iH Attributes
  225. .PP
  226. The DLG scanner matches keywords, \f(CWWORD\fP's, etc... on the input
  227. stream.  The way ANTLR parsers access that text
  228. is though the attribute mechanism.  Attributes are run-time objects
  229. associated will all grammar elements (items to the right of the \f(CW:\fP
  230. in a rule definition).  Although attributes are associated with subrules
  231. and rule references, only those attributes linked to grammar tokens are
  232. of interest to us.  Attributes are denoted \f(CW$\fP\fIi\fP where \fIi\fP
  233. is the grammar element \fIi\fP positions from the start of the alternative.
  234. The user must define an attribute type called \f(CWAttrib\fP.  This type
  235. is most often some sort of string whether constant or dynamically allocated.
  236. For simplicity, we employ a standard attribute type available with the
  237. PCCTS system.  Attributes are structures that contain a
  238. constant width (30 character) string.  By placing the character array
  239. inside of a structure, the entire string can be copied like any simple
  240. C variable.  The ANTLR pseudo-op \f(CW#header\fP is used to describe
  241. attributes and other information that must be present in all generated
  242. C files.  In our case, we simply need to include the standard
  243. text attribute definition.  This pseudo-op must occur first in the
  244. grammar file if it exists at all.
  245. .cB
  246. #header <<#include "charbuf.h">>
  247. .cE
  248. .NH 2
  249. .iH Grammatical analysis
  250. .PP
  251. This subsection describes the grammatical or syntactic aspects of \fIsc\fP.
  252. No symbol table management is used and therefore functions and variables
  253. are considered simple \f(CWWORD\fP's.  Later versions of the grammar
  254. can use the tokens \f(CWVAR\fP and \f(CWFUNC\fP.
  255. .NH 3
  256. .iH Definitions, variables
  257. .PP
  258. An \fIsc\fP program is a sequence of definitions\(emvariables or functions:
  259. .cB
  260. p       :   ( func | "var" def ";" )* ;
  261. .cE
  262. .LP
  263. The \f(CW( )*\fP subrule means that there are zero or more definitions.
  264. The \f(CW|\fP operator starts a new alternative.
  265. .PP
  266. The grammar for a variable definitions is broken up between the rule
  267. \f(CWp\fP and \f(CWdef\fP so that \f(CWdef\fP can be reused for
  268. parameter definitions (it also makes more sense when code generation
  269. has been added).
  270. .cB
  271. def     :   WORD ;
  272. .cE
  273. .NH 3
  274. .iH Functions
  275. .PP
  276. \fIsc\fP functions follow C's format except that the default
  277. return type is a string instead of \f(CWint\fP.  
  278. .cB
  279. func    :   WORD "\e(" { WORD } "\e)"
  280.             "\e{"
  281.                 ( def )*
  282.                 ( statement )*
  283.             "\e}"
  284.         ;
  285. .cE
  286. .LP
  287. Note that the parentheses and the curly-braces must be escaped
  288. with \f(CW\e\fP because they are special regular expression symbols.
  289. .NH 3
  290. .iH Statements
  291. .PP
  292. The statements outlined in the \fIsc\fP language definition can be
  293. described with
  294. .cB
  295. statement
  296.         :   expr ";"
  297.         |   "\e{" ( statement )* "\e}"
  298.         |   "if" "\e(" expr "\e)" statement {"else" statement}
  299.         |   "while" "\e(" expr "\e)" statement
  300.         |   "return" expr ";"
  301.         |   "print" expr ";"
  302.         ;
  303. .cE
  304. .LP
  305. where \f(CW{ }\fP means optional.
  306. .NH 3
  307. .iH Expressions
  308. .PP
  309. The operators and expression atoms described in the language definition
  310. can be recognized by the following grammar fragment.
  311. .cB
  312. expr    :   WORD "=" expr
  313.         |   expr0
  314.         ;
  315.  
  316. expr0   :   expr1 ( ("=="|"!=") expr1 )*
  317.         ;
  318.  
  319. expr1   :   expr2 ( ("\e+"|"\e-") expr2 )*
  320.         ;
  321.  
  322. expr2   :   expr3 ( ("\e*"|"/") expr3 )*
  323.         ;
  324.  
  325. expr3   :   {"\e-"} expr4
  326.         ;
  327.  
  328. expr4   :   STRING
  329.         |   WORD { "\e(" { expr } "\e)" }
  330.         |   "\e(" expr "\e)"
  331.         ;
  332. .cE
  333. .LP
  334. Rule \f(CWexpr\fP is ambiguous if we only look one token into the
  335. future since \f(CWWORD\fP can also be an \f(CWexpr0\fP.  However, if
  336. we were to tell ANTLR to use two tokens, it could see that the
  337. \f(CW"="\fP assignment operator uniquely identifies which alternative
  338. to match when \f(CWWORD\fP is the first token of lookahead.  Rule
  339. \f(CWexpr\fP makes this grammar LL(2); but, we only use the extra
  340. token of lookahead in \f(CWexpr\fP (leaving all others LL(1)).  Please
  341. note the use of ANTLR's command-line option \*Q\f(CW-k 2\fP\*U in the
  342. makefiles presented below.
  343. .PP
  344. ANTLR does not have a method of explicitly outlining operator precedence.
  345. Instead precedence is implicitly defined by the rule invocation sequence
  346. or abstractly by the parse-tree.  Rule \f(CWexpr\fP calls
  347. \f(CWexpr0\fP which calls \f(CWexpr1\fP etc... nesting more
  348. and more deeply.  The precedence rule-of-thumb in ANTLR (and any LL-type
  349. parser) is: the deeper the nesting level, the higher the precedence (the
  350. more tightly the operator binds).  Operators in the expression starting
  351. rule have the lowest precedence whereas operators in the last rule
  352. in the expression recursion have the highest precedence.  This becomes
  353. obvious when a parse-tree for some input text is examined.
  354. .PP
  355. Once again, note that the operators for \fIsc\fP must be escaped as they are
  356. reserved regular expression operators as well.
  357. .bp
  358. .NH 2
  359. .iH Complete ANTLR description (w/o symbol table management)
  360. .PP
  361. The following code is the complete ANTLR description to recognize \fIsc\fP
  362. programs.  Nothing is added to the symbol table and undefined
  363. variables/functions are not flagged.
  364. .cB
  365. #header <<#include "charbuf.h">>
  366.  
  367. #token "[\et\e ]+"    << zzskip(); >>                /* Ignore White */
  368. #token "\en"         << zzline++; zzskip(); >>
  369. #token STRING "\e"(~[\e0-\e0x1f\e"\e\e]|(\e\e~[\e0-\e0x1f]))*\e"" <<;>>
  370.  
  371. << main() { ANTLR(p(), stdin); } >>
  372.  
  373. p       :   ( func | "var" def ";" )*
  374.             "@"
  375.         ;
  376.  
  377. def     :   WORD
  378.         ;
  379.  
  380. func    :   WORD "\e(" { def } "\e)"
  381.             "\e{"
  382.                 ( "var" def ";" )*
  383.                 ( statement )*
  384.             "\e}"
  385.         ;
  386.  
  387. statement
  388.         :   expr ";"
  389.         |   "\e{" ( statement )* "\e}"
  390.         |   "if" "\e(" expr "\e)" statement {"else" statement}
  391.         |   "while" "\e(" expr "\e)" statement
  392.         |   "return" expr ";"
  393.         |   "print" expr ";"
  394.         ;
  395.  
  396. expr    :   WORD "=" expr
  397.         |   expr0
  398.         ;
  399.  
  400. expr0   :   expr1 ( ("==" | "!=") expr1 )*
  401.         ;
  402.  
  403. expr1   :   expr2 ( ("\e+" | "\e-") expr2 )*
  404.         ;
  405.  
  406. expr2   :   expr3 ( ( "\e*" | "/" ) expr3 )*
  407.         ;
  408.  
  409. expr3   :   {"\e-" } expr4
  410.         ;
  411.  
  412. expr4   :   STRING
  413.         |   WORD { "\e(" { expr } "\e)" }
  414.         |   "\e(" expr "\e)"
  415.         ;
  416.  
  417. #token WORD "[a-zA-Z]+"
  418. .cE
  419. .NH 2
  420. .iH Makefile
  421. .PP
  422. The following makefile can be used to make the above language description
  423. into an executable file.  We assume that the ANTLR includes and standard
  424. attribute packages are located in a directory accessible to us as
  425. \f(CW../h\fP.  The grammar listed above must be in file
  426. \f(CWtut1.g\fP.
  427. .cB
  428. #
  429. # Makefile for 1.00 tutorial (no symbol table stuff)
  430. # ANTLR creates parser.dlg, err.c, tut1.c, tokens.h
  431. # DLG creates scan.c, mode.h
  432. #
  433. CFLAGS= -I../h
  434. GRM=tut1
  435. SRC=scan.c $(GRM).c err.c
  436. OBJ=scan.o $(GRM).o err.o
  437.  
  438. tutorial: $(OBJ) $(SRC)
  439.     cc -o $(GRM) $(OBJ)
  440.  
  441. # build a parser and lexical description from a language description
  442. $(GRM).c parser.dlg : $(GRM).g
  443.     antlr -k 2 $(GRM).g
  444.  
  445. # build the scanner from a lexical description
  446. scan.c : parser.dlg
  447.     dlg -C2 parser.dlg scan.c
  448. .cE
  449. .LP
  450. Remember that \f(CWmake\fP wants a tab, not spaces, in front of the
  451. action statements (e.g. \f(CWcc\fP, \f(CWantlr\fP, ...).
  452. .NH 2
  453. .iH Testing
  454. .PP
  455. After successful completion of \f(CWmake\fP, the executable
  456. \f(CWtut\fP will exist in the current directory.  \f(CWtut\fP takes
  457. input from \f(CWstdin\fP.  Therefore, one parses a file via
  458. .cB
  459. tut < \fIfile\fP.sc
  460. .cE
  461. .LP
  462. The prompt will return without a message if no syntax errors were
  463. discovered.  However, if \fIfile\fP contains lexical or syntactic
  464. errors, error messages will appear.  We have given no instructions
  465. related to translation, so nothing happens if all is well.
  466. .NH 2
  467. .iH Symbol table management
  468. .PP
  469. The grammar presented thus far can only recognize \fIsc\fP programs.
  470. No translation is possible because it does not deal with the semantics
  471. of the input program only its structure.  To begin semantic
  472. interpretation, one must add new symbols to a symbol table.  The
  473. symbols required to \*Qunderstand\*U an \fIsc\fP program are
  474. .IP \f(CWVAR\fP 10n
  475. Symbol is a local (denoted with the \f(CW#define\fP constant \f(CWLOCAL\fP),
  476. a parameter (\f(CWPARAMETER\fP) or global (\f(CWGLOBAL\fP) variable.
  477. .IP \f(CWFUNC\fP 10n
  478. Symbol is a function whose level is always \f(CWGLOBAL\fP.
  479. .PP
  480. A symbol table record requires two fields: \f(CWtoken\fP which indicates
  481. either \f(CWVAR\fP or \f(CWFUNC\fP and \f(CWlevel\fP which is either
  482. \f(CWLOCAL\fP, \f(CWPARAMETER\fP or \f(CWGLOBAL\fP.
  483. .PP
  484. The PCCTS system comes with a simple symbol table manager.  The source
  485. is documented well and its functions will be referenced without
  486. explanation here.  To use the functions, our grammar must include a
  487. file called \f(CWsym.h\fP and define a symbol table structure.  We
  488. shall put the \f(CW#include\fP in the \f(CW#header\fP directive.
  489. .cB
  490. #header <<#include "sym.h"
  491.           #include "charbuf.h">>
  492. .cE
  493. .LP
  494. The file \f(CWsym.c\fP contains the actual functions and must be
  495. linked into your executable.  Our makefile will handle this
  496. automatically.  The \f(CWsym.c\fP can be found in the
  497. \f(CWsupport/sym\fR subdirectory of the standard PCCTS installation;
  498. this should be copied into the tutorial directory.
  499. .PP
  500. The symbol table manager requires a number of fields within the symbol
  501. table entry.  A template has been provided that the user can copy into
  502. their work directory and modify.  The template in \f(CWsym.h\fP will
  503. be modified in our case to include the two fields mentioned
  504. above\(em\f(CWtoken\fP and \f(CWlevel\fP.
  505. .cB
  506. typedef struct symrec {
  507.             char *symbol;
  508.             struct symrec *next, *prev, **head, *scope;
  509.             int token;  /* either FUNC or VAR */
  510.             int level;  /* either LOCAL, GLOBAL, PARAMETER */
  511.             int offset; /* offset from sp on the stack */
  512.                         /* locals are - offset, param is 0 */
  513.                         /* used only in tut4; reserved */
  514.         } Sym, *SymPtr;
  515. .cE
  516. .LP
  517. We add the following definitions to the front of our grammar.
  518. .cB
  519. <<
  520. #define HashTableSize       999
  521. #define StringTableSize     5000
  522. #define GLOBAL              0
  523. #define PARAMETER           1
  524. #define LOCAL               2
  525.  
  526. static Sym *globals = NULL;        /* global scope for symbols */
  527. >>
  528. .cE
  529. where \f(CWglobals\fP is used to track all global symbols
  530. (functions and variables).  Also, to print out symbol scopes, we
  531. define a function called \f(CWpScope(Sym\ *p)\fP that dumps a scope to
  532. \f(CWstdout\fP.  It's implementation is unimportant and given with
  533. the full grammar description listed below.  To initialize the symbol
  534. table, we add a function call to the symbol table manager library
  535. yielding a new \f(CWmain()\fP.
  536. .cB
  537. main()
  538. {
  539.     zzs_init(HashTableSize, StringTableSize);
  540.     ANTLR(p(), stdin);
  541. }
  542. .cE
  543. .PP
  544. When a variable, parameter or function is defined, we want to add that
  545. symbol to the symbol table.  We shall treat parameters like variables
  546. grammatically and use field \f(CWlevel\fP to differentiate between
  547. them.  When a \f(CWWORD\fP is found in rule \f(CWdef\fP, we will add
  548. it to the symbol table using the scope and level passed into
  549. \f(CWdef\fP.  The situation is complicated slightly by the fact that a
  550. local variable may have the same name as a global variable.  Scopes
  551. are linked lists that weave through the symbol table grouping all
  552. entries within the same scope.  Our grammar for rule \f(CWdef\fP
  553. becomes:
  554. .cB
  555. def[Sym **scope, int level] : <<Sym *var;>> (WORD | VAR) ;
  556. .cE
  557. .LP
  558. where the init-action defines a local variable called \f(CWvar\fP.
  559. .PP
  560. To handle the definition of previously unknown symbols, we add an
  561. action after the \f(CWWORD\fP reference.
  562. .cB
  563. ( WORD
  564.   <<zzs_scope($scope);         /* set current scope to scope passed in */
  565.     var = zzs_newadd($1.text); /* create entry, add text of WORD to table */
  566.     var->level = $level;       /* set the level to level passed in */
  567.     var->token = VAR;          /* symbol is a variable */
  568.   >>
  569. | VAR
  570. )
  571. .cE
  572. .LP
  573. To deal with a symbol defined in another scope we add the following
  574. action to the \f(CWVAR\fP reference.
  575. .cB
  576. ( WORD
  577.   <<...>>
  578. | VAR
  579.   <<var = zzs_get($1.text);    /* get previous definition */
  580.     if ( level != var->level ) /* make sure we have a diff scope */
  581.     {
  582.       zzs_scope($scope);       /* same here as above for unknown */
  583.       var = zzs_newadd($1.text);
  584.       var->level = $level;
  585.       var->token = VAR;
  586.     }
  587.     else printf("redefined variable ignored: %s\en", $1.text);
  588.   >>
  589. )
  590. .cE
  591. .LP
  592. Note that this implies that the lexical analyzer will modify the token
  593. number according to its definition in the symbol table (if any).  This
  594. is generally not a good idea, but can be quite helpful when trying to
  595. remove nasty ambiguities in your grammar.  Typically more than one
  596. token of lookahead makes it unnecessary to use \*Qderived\*U tokens.
  597. We do so here to illustrate the interaction of lexical analyzer and
  598. parser.
  599. .PP
  600. Rule \f(CWp\fP must be modified to pass a scope and level to rule
  601. \f(CWdef\fP.  In addition, we will remove the global scope at the end
  602. of parsing and print out the symbols.
  603. .cB
  604. p       :   <<Sym *p;>>
  605.             ( func | "var" def[&globals, GLOBAL] ";" )*
  606.             <<p = zzs_rmscope(&globals);
  607.               printf("Globals:\en");
  608.               if ( p != NULL ) pScope(p);
  609.             >>
  610.             "@"
  611.         ;
  612. .cE
  613. .PP
  614. Rule \f(CWfunc\fP now must create a \f(CWFUNC\fP symbol table entry
  615. and define a \f(CWVAR\fP entry for its parameter if one exists.  Rule
  616. \f(CWfunc\fP checks for duplicate \f(CWFUNC\fP entries by only
  617. matching unknown \f(CWWORD\fP's.  If a function had been previously
  618. defined, its token would be \f(CWFUNC\fP.
  619. .cB
  620. func    :   <<Sym *locals=NULL, *var, *p;>>
  621.             WORD
  622.             <<zzs_scope(&globals);
  623.               var = zzs_newadd($1.text);
  624.               var->level = GLOBAL;
  625.               var->token = FUNC;
  626.             >>
  627.             "\e(" { def[&locals, PARAMETER] } "\e)"
  628.             "\e{"
  629.                  ( "var" def[&locals, LOCAL] ";" )*
  630.                  ( statement )*
  631.             "\e}"
  632.             <<p = zzs_rmscope(&locals);
  633.               printf("Locals for %s:\en", $1.text);
  634.               if ( p != NULL ) pScope(p);
  635.             >>
  636.         ;
  637. .cE
  638. .LP
  639. At the end of the function, we remove the local scope of variables
  640. (and parameter if it exists) and print the symbols out to
  641. \f(CWstdout\fP.
  642. .PP
  643. When a \f(CWWORD\fP is encountered on the input stream, we need to look
  644. it up in the symbol table to find out whether it is a variable
  645. (parameter) or a function.  The token number needs to be changed
  646. accordingly before the parser sees it so that it will not try to match
  647. a \f(CWWORD\fP.  Any \f(CWWORD\fP references in an expression that are
  648. not defined in the symbol table are undefined variables.  We
  649. accomplish this token \*Qderivation\*U strategy by attaching an action
  650. to the regular expression for \f(CWWORD\fP.
  651. .cB
  652. #token WORD "[a-zA-Z]+"
  653.     <<{
  654.         Sym *p = zzs_get(LATEXT(1));
  655.         if ( p != NULL ) NLA = p->token;
  656.     }>>
  657. .cE
  658. .LP
  659. The macro \f(CWLATEXT(1)\fP is always set to the text matched on the
  660. input stream for the current token.  \f(CWNLA\fP is the next token of
  661. look-ahead.  We need to change this from \f(CWWORD\fP to whatever is
  662. found in the symbol table.
  663. .PP
  664. Rules for statements and expressions do not change when adding symbol
  665. table management because they simply apply a structure to grammar
  666. symbols and do not introduce new ones.
  667. .NH 2
  668. .iH Complete ANTLR description (with symbol table management)
  669. .PP
  670. The following code is the complete ANTLR description to recognize \fIsc\fP
  671. programs.  Functions, variables and parameters are added to the symbol
  672. table and are printed to \f(CWstdout\fP after function definitions and at the
  673. end of the \fIsc\fP program.
  674. .cB
  675. #header <<
  676.     #include "sym.h"
  677.     #include "charbuf.h"
  678. >>
  679.  
  680. #token "[\et\e ]+"    << zzskip(); >>                /* Ignore White */
  681. #token "\en"         << zzline++; zzskip(); >>
  682. #token STRING "\e"(~[\e0-\e0x1f\e"\e\e]|(\e\e~[\e0-\e0x1f]))*\e"" <<;>>
  683.  
  684. <<
  685. #define HashTableSize       999
  686. #define StringTableSize     5000
  687. #define GLOBAL              0
  688. #define PARAMETER           1
  689. #define LOCAL               2
  690.  
  691. static Sym *globals = NULL; /* global scope for symbols */
  692. .cE
  693. .cB
  694. main()
  695. {
  696.     zzs_init(HashTableSize, StringTableSize);
  697.     ANTLR(p(), stdin);
  698. }
  699.  
  700. pScope(p)
  701. Sym *p;
  702. {
  703.     for (; p!=NULL; p=p->scope)
  704.     {
  705.         printf("\etlevel %d | %-12s | %-15s\en",
  706.             p->level,
  707.             zztokens[p->token],
  708.             p->symbol);
  709.     }
  710. }
  711. >>
  712. .cE
  713. .cB
  714. p       :   <<Sym *p;>>
  715.             ( func | "var" def[&globals, GLOBAL] ";" )*
  716.             <<p = zzs_rmscope(&globals);
  717.               printf("Globals:\en");
  718.               pScope(p);
  719.             >>
  720.             "@"
  721.         ;
  722.  
  723. def[Sym **scope, int level]
  724.         :   <<Sym *var;>>
  725.             (   WORD
  726.                 <<zzs_scope($scope);
  727.                   var = zzs_newadd($1.text);
  728.                   var->level = $level;
  729.                   var->token = VAR;
  730.                 >>
  731.             |   VAR
  732.                 <<var = zzs_get($1.text);
  733.                   if ( $level != var->level )
  734.                   {
  735.                     zzs_scope($scope);
  736.                     var = zzs_newadd($1.text);
  737.                     var->level = $level;
  738.                     var->token = VAR;
  739.                   }
  740.                   else printf("redefined variable ignored: %s\en", $1.text);
  741.                 >>
  742.             )
  743.         ;
  744. .cE
  745. .cB
  746. func    :   <<Sym *locals=NULL, *var, *p;>>
  747.             WORD
  748.             <<zzs_scope(&globals);
  749.               var = zzs_newadd($1.text);
  750.               var->level = GLOBAL;
  751.               var->token = FUNC;
  752.             >>
  753.             "\e(" { def[&locals, PARAMETER] } "\e)"
  754.             "\e{"
  755.                 ( "var" def[&locals, LOCAL] ";" )*
  756.                 ( statement )*
  757.             "\e}"
  758.             <<p = zzs_rmscope(&locals);
  759.               printf("Locals for %s:\en", $1.text);
  760.               pScope(p);
  761.             >>
  762.         ;
  763.  
  764. statement
  765.         :   expr ";"
  766.         |   "\e{" ( statement )* "\e}"
  767.         |   "if" "\e(" expr "\e)" statement
  768.             {"else" statement}
  769.         |   "while" "\e(" expr "\e)" statement
  770.         |   "return" expr ";"
  771.         |   "print" expr ";"
  772.         ;
  773. .cE
  774. .cB
  775. expr    :   VAR "=" expr
  776.         |   expr0
  777.         ;
  778.  
  779. expr0   :   expr1 ( (   "=="
  780.                     |   "!="
  781.                     )
  782.                     expr1
  783.                   )*
  784.         ;
  785.  
  786. expr1   :   expr2 ( (   "\e+"
  787.                     |   "\e-"
  788.                     )
  789.                     expr2
  790.                   )*
  791.         ;
  792.  
  793. expr2   :   expr3 ( (   "\e*"
  794.                     |   "/"
  795.                     )
  796.                     expr3
  797.                   )*
  798.         ;
  799.  
  800. expr3   :   {"\e-" } expr4
  801.         ;
  802. .cE
  803. .cB
  804. expr4   :   STRING
  805.         |   VAR
  806.         |   (   FUNC
  807.             |   WORD
  808.             )
  809.             "\e(" { expr } "\e)"
  810.         |   "\e(" expr "\e)"
  811.     ;
  812.  
  813. #token WORD "[a-zA-Z]+"
  814.     <<{
  815.         Sym *p = zzs_get(LATEXT(1));
  816.         if ( p != NULL ) NLA = p->token;
  817.     }>>
  818. .cE
  819. .NH 2
  820. .iH File \f(CWsym.h\fP
  821. .PP
  822. The following is a modification of the \f(CWsym.h\fP template provided
  823. with PCCTS.  The fields of the symbol table entry structure have
  824. augmented for our purposes as outlined above.
  825. .cB
  826. /* define some hash function */
  827. #ifndef HASH
  828. #define HASH(p, h) while ( *p != '\e0' ) h = (h<<1) + *p++;
  829. #endif
  830.  
  831. typedef struct symrec {
  832.             char * symbol;
  833.             struct symrec *next, *prev, **head, *scope;
  834.             unsigned hash;
  835.             int token;  /* either FUNC or VAR */
  836.             int level;  /* either LOCAL, GLOBAL, PARAMETER */
  837.             int offset; /* offset from sp on the stack */
  838.                         /* locals are - offset, param is 0 */
  839.                         /* used only tut4; reserved */
  840.         } Sym, *SymPtr;
  841.  
  842. void zzs_init();
  843. void zzs_done();
  844. void zzs_add();
  845. Sym *zzs_get();
  846. void zzs_del();
  847. void zzs_keydel();
  848. Sym **zzs_scope();
  849. Sym *zzs_rmscope();
  850. void zzs_stat();
  851. Sym *zzs_new();
  852. Sym *zzs_newadd();
  853. char *zzs_strdup();
  854. .cE
  855. .NH 2
  856. .iH Makefile (for use with symbol table management)
  857. .PP
  858. The following makefile can be used to make the above language description
  859. into an executable file.  We assume that the ANTLR includes and standard
  860. attribute packages are located in a directory accessible to us as
  861. \f(CW../h\fP.  Also, \f(CWsym.c\fP, \f(CWsym.h\fP are located in the
  862. current working directory.  The grammar listed above must be in file
  863. \f(CWtut2.g\fP.
  864. .cB
  865. #
  866. # Makefile for 1.00 tutorial
  867. # ANTLR creates parser.dlg, err.c, tut1.c
  868. # DLG creates scan.c
  869. #
  870. CFLAGS= -I../h
  871. GRM=tut2
  872. SRC=scan.c $(GRM).c err.c sym.c
  873. OBJ=scan.o $(GRM).o err.o sym.o
  874.  
  875. tutorial: $(OBJ) $(SRC)
  876.     cc -o $(GRM) $(OBJ)
  877.  
  878. $(GRM).c parser.dlg : $(GRM).g
  879.     antlr -k 2 $(GRM).g
  880.  
  881. scan.c : parser.dlg
  882.     dlg -C2 parser.dlg scan.c
  883. .cE
  884. .NH 2
  885. .iH Sample input/output
  886. .PP
  887. The current state of the program accepts input like the following
  888. sample.
  889. .cB
  890. var i;
  891. var j;
  892.  
  893. f(k)
  894. {
  895.     var local;
  896.     var j;
  897.  
  898.     if ( "true" ) local = "zippo";
  899. }
  900.  
  901. g()
  902. {
  903.     var note;
  904.  
  905.     note = "1";
  906.     while ( note )
  907.     {
  908.         i = "456";
  909.     }
  910. }
  911. .cE
  912. .LP
  913. The output of our executable, \f(CWtut\fP, would be
  914. .cB
  915. Locals for f:
  916.         level 2 | VAR          | j              
  917.         level 2 | VAR          | local          
  918.         level 1 | VAR          | k              
  919. Locals for g:
  920.         level 2 | VAR          | note           
  921. Globals:
  922.         level 0 | FUNC         | g              
  923.         level 0 | FUNC         | f              
  924.         level 0 | VAR          | j              
  925.         level 0 | VAR          | i              
  926. .cE
  927. .LP
  928. Note that the parameter \f(CWk\fP is level 1 for \f(CWPARAMETER\fP
  929. and the local variable \f(CWlocal\fP is level 2 for \f(CWLOCAL\fP.
  930. .NH
  931. .iH Translate \fIsc\fP to stack code
  932. .PP
  933. Generating code for a stack machine is simple and can be done by
  934. simply adding \f(CWprintf()\fP actions to the grammar in the
  935. appropriate places.
  936. .PP
  937. We begin with a discussion of the stack machine and how to generate
  938. code for it.  Next we augment our grammar with actions to dump stack
  939. code to \f(CWstdout\fP.
  940. .NH 2
  941. .iH A simple stack machine for \fIsc\fP
  942. .PP
  943. Our stack machine consists of a single CPU, a finite stack of strings,
  944. a finite memory, a stack pointer (\f(CWsp\fP) and a frame pointer
  945. (\f(CWfp\fP).  All data items used by stack programs are strings
  946. (currently set to a maximum length of 100).  Our string stack grows
  947. downwards towards 0 from the maximum stack height.
  948. .PP
  949. To make implementation simple, our stack code will actually be a
  950. sequence of macro invocations in a C program.  This way C will take
  951. care of control-flow and allocating space etc...  The minimum stack
  952. code program defines a \f(CW_main\fP and includes \f(CWsc.h\fP which
  953. contains all of the stack code macros:
  954. .cB
  955. #include "sc.h"
  956. _main()
  957. {
  958.     BEGIN;
  959.     END;
  960. }
  961. .cE
  962. .LP
  963. The \f(CWBEGIN\fP and \f(CWEND\fP macros are explained below.
  964. .NH 3
  965. .iH Functions
  966. .PP
  967. Every \fIsc\fP program requires a \f(CWmain\fP which will we translate
  968. to \f(CW_main\fP (a C function \f(CWmain\fP will call \f(CW_main\fP).
  969. Other functions are translated verbatim.  The parameter to your main
  970. program will be the first command line argument when you execute your
  971. \fIsc\fP program (after translation to C).  If no command line
  972. argument is specified, a \f(CW""\fP is pushed.
  973. .PP
  974. Parameters are pushed on the string stack before a function is called,
  975. so no argument is needed to the resulting C function.  Return values
  976. are implicitly strings but are also returned on the string stack\ \(em
  977. avoiding the need to define a return type of the C function.  An
  978. \*Qinstruction\*U (macro) called \f(CWBEGIN\fP is executed before any
  979. other in a function.  This saves the current frame pointer and then
  980. makes it point to the argument passed into the function.  \f(CWEND\fP
  981. is used to restore the frame pointer to its previous value and make
  982. the stack pointer point to the return value.  After a function call,
  983. the top of stack is always the return value.
  984. .PP
  985. Arguments and local variables are at offsets to the frame pointer.
  986. The optional argument is at offset 0.  The first local variable is at
  987. offset 1, the second at offset 2 and so on.  Graphically,
  988. .cB
  989.        |    .      |
  990.        |    .      |
  991.        |   arg     |   fp + 0
  992.        | 1st local |   fp - 1
  993.        | 2nd local |   fp - 2
  994.        |   ...     |
  995.        |    .      |
  996.        |    .      |
  997. .cE
  998. .LP
  999. A dummy argument is pushed by the calling function if no argument is
  1000. specified.
  1001. .PP
  1002. To translate a function,
  1003. .cB
  1004. \fIf\fP(\fIarg\fP)
  1005. {
  1006. }
  1007. .cE
  1008. .LP
  1009. we simply dump the following
  1010. .cB
  1011. \fIf\fP()
  1012. {
  1013.     BEGIN;
  1014.     END;
  1015. }
  1016. .cE
  1017. .LP
  1018. Note that the argument disappears because we pass arguments on the
  1019. string stack not the C hardware stack.
  1020. .NH 3
  1021. .iH Variables
  1022. .PP
  1023. Global variables of the form
  1024. .cB
  1025. var \fIname\fP;
  1026. .cE
  1027. .LP
  1028. are translated to
  1029. .cB
  1030. SCVAR \fIname\fP;
  1031. .cE
  1032. .LP
  1033. where SCVAR is a C type defined in \f(CWsc.h\fP that makes space for a
  1034. \fIsc\fP variable.
  1035. .PP
  1036. Local variables are allocated on the string stack and are created at
  1037. run time via the instruction \f(CWLOCAL\fP.  Each execution of
  1038. \f(CWLOCAL\fP allocates space for one more local variable on the
  1039. stack.  \f(CWLOCAL\fP's must be executed after the \f(CWBEGIN\fP but
  1040. before any other stack code instruction.  The \f(CWEND\fP macro resets
  1041. the stack pointer so that these locals disappear after each function
  1042. invocation.  For example,
  1043. .cB
  1044. main()
  1045. {
  1046.     var i;
  1047.     var j;
  1048. }
  1049. .cE
  1050. .LP
  1051. is translated to:
  1052. .cB
  1053. #include "sc.h"
  1054. _main()
  1055. {
  1056.     BEGIN;
  1057.     LOCAL;
  1058.     LOCAL;
  1059.     END;
  1060. }
  1061. .cE
  1062. .NH 3
  1063. .iH Expressions
  1064. .PP
  1065. Operator precedence is defined implicitly in top-down (LL) grammars.
  1066. The deeper the level of recursion, the higher the precedence.  To
  1067. generate code for operators, one prints out the correct macro for that
  1068. operator after the two operators have been seen (because we are
  1069. generating code for a stack machine).  If the operator is a unary
  1070. operator like negate, we wait until the operand is seen and then print
  1071. the operator.  For instance, \f(CWexpr1\fP,
  1072. .cB
  1073. expr1   :   expr2 ( ("\e+"|"\e-") expr2)*
  1074.         ;
  1075. .cE
  1076. .LP
  1077. would be translated as:
  1078. .cB
  1079. expr1   :   <<char *op;>>
  1080.             expr2 ( (   "\e+" <<op="ADD";>>
  1081.                     |   "\e-" <<op="SUB";>>
  1082.                     )
  1083.                     expr2
  1084.                     <<printf("\et%s;\en", op);>>
  1085.                   )*
  1086.         ;
  1087.  
  1088. .cE
  1089. .LP
  1090. where \f(CWADD\fP and \f(CWSUB\fP are \fIsc\fP stack machine macros
  1091. defined below.
  1092. .PP
  1093. The assignment operator groups right to left and must generate code
  1094. that duplicates itself after each assignment so that the value of the
  1095. expression is on the stack for any chained assignement.  For example,
  1096. .cB
  1097. main()
  1098. {
  1099.     var a;
  1100.     var b;
  1101.  
  1102.     a = b = "test";
  1103. }
  1104. .cE
  1105. .LP
  1106. would be translated to:
  1107. .cB
  1108. #include "sc.h"
  1109. _main()             /* main() */
  1110. {
  1111.     BEGIN;
  1112.     LOCAL;          /* var a; */
  1113.     LOCAL;          /* var b; */
  1114.     SPUSH("test");  /* a = b = "test"; */
  1115.     DUP;
  1116.     LSTORE(2);      /* store into b */
  1117.     DUP;
  1118.     LSTORE(1);      /* store into a */
  1119.     POP;
  1120.     END;
  1121. }
  1122. .cE
  1123. .PP
  1124. Since an expression is a statement, it is possible that a value could
  1125. be left on the stack.  For example,
  1126. .cB
  1127. main()
  1128. {
  1129.     "expression";
  1130. }
  1131. .cE
  1132. .LP
  1133. We must pop this extraneous value off the stack:
  1134. .cB
  1135. #include "sc.h"
  1136. _main()
  1137. {
  1138.     BEGIN;
  1139.     SPUSH("expression");
  1140.     POP;
  1141.     END;
  1142. }
  1143. .cE
  1144. .NH 3
  1145. .iH Instructions
  1146. .PP
  1147. All instructions take operands from the stack and return results on the
  1148. stack.  Some have no side effects on the stack but alter the C program
  1149. counter.
  1150. .IP \f(CWPUSH(\fIv\f(CW)\fR 12n
  1151. Push the value of variable \fIv\fP onto the stack.
  1152. .IP \f(CWSPUSH(\fIs\f(CW)\fR 12n
  1153. Push the value of the string constant \fIs\fP onto the stack.
  1154. .IP \f(CWLPUSH(\fIn\f(CW)\fR 12n
  1155. Push the value of the local variable or function argument at offset
  1156. \fIn\fP onto the stack.
  1157. .IP \f(CWSTORE(\fIv\f(CW)\fR 12n
  1158. Pop the top of stack and store it into variable \fIv\fP.
  1159. .IP \f(CWLSTORE(\fIn\f(CW)\fR 12n
  1160. Pop the top of stack and store it into local variable or function
  1161. argument at offset \fIn\fP.
  1162. .IP \f(CWPOP\fR 12n
  1163. Pop the top of stack; stack is one string smaller.  No side effects
  1164. with data memory.
  1165. .IP \f(CWLOCAL\fR 12n
  1166. Create space on the stack for a local variable.  Must appear after
  1167. \f(CWBEGIN\fP but before any other instruction in a function.
  1168. .IP \f(CWBRF(\fIa\f(CW)\fR 12n
  1169. Branch, if top of stack is \f(CW"false"\fP or \f(CW"0"\fP, to
  1170. \*Qaddress\*U \fIa\fP (C label); top of stack is popped off.
  1171. .IP \f(CWBRT(\fIa\f(CW)\fR 12n
  1172. Branch, if top of stack is \f(CW"true"\fP or \f(CW"1"\fP, to
  1173. \*Qaddress\*U \fIa\fP (C label); top of stack is popped off.
  1174. .IP \f(CWBR(\fIa\f(CW)\fR 12n
  1175. Branch to \*Qaddress\*U \fIa\fP (C label).  Stack is not touched.
  1176. .IP \f(CWCALL(\fIf\f(CW)\fR 12n
  1177. Call the function \fIf\fP.  Returns with result on stack top.
  1178. .IP \f(CWPRINT\fR 12n
  1179. Pop the top of stack and print the string to \f(CWstdout\fP.
  1180. .IP \f(CWRETURN\fR 12n
  1181. Set the return value to the top of stack.  Return from the function.
  1182. .IP \f(CWEQ\fR 12n
  1183. Perform \f(CWstack[sp] = (stack[sp+1] == stack[sp])\fP.
  1184. .IP \f(CWNEQ\fR 12n
  1185. Perform \f(CWstack[sp] = (stack[sp+1] != stack[sp])\fP.
  1186. .IP \f(CWADD\fR 12n
  1187. Perform \f(CWstack[sp] = (stack[sp+1] + stack[sp])\fP.
  1188. .IP \f(CWSUB\fR 12n
  1189. Perform \f(CWstack[sp] = (stack[sp+1] - stack[sp])\fP.
  1190. .IP \f(CWMUL\fR 12n
  1191. Perform \f(CWstack[sp] = (stack[sp+1] * stack[sp])\fP.
  1192. .IP \f(CWDIV\fR 12n
  1193. Perform \f(CWstack[sp] = (stack[sp+1] / stack[sp])\fP.
  1194. .IP \f(CWNEG\fR 12n
  1195. Perform \f(CWstack[sp] = -stack[sp]\fP.
  1196. .IP \f(CWDUP\fR 12n
  1197. Perform \f(CWPUSH(stack[sp])\fP.
  1198. .IP \f(CWBEGIN\fR 12n
  1199. Function preamble.
  1200. .IP \f(CWEND\fR 12n
  1201. Function cleanup.
  1202. .PP
  1203. Boolean operations yield string constants \f(CW"false"\fP for false
  1204. and \f(CWtrue\fR for true.  All other operations yield string
  1205. constants representing numerical values (\f(CW"3"+"4"\fP is
  1206. \f(CW"7"\fP).
  1207. .NH 2
  1208. .iH Examples
  1209. .PP
  1210. The sample factorial program from above,
  1211. .cB
  1212. main(n)
  1213. {
  1214.     print fact(n);
  1215.     print "\en";
  1216. }
  1217.  
  1218. fact(n)
  1219. {
  1220.     if ( n == "0" ) return "1";
  1221.     return n * fact(n - "1");
  1222. }
  1223. .cE
  1224. .LP
  1225. would be translated to:
  1226. .cB
  1227. #include "sc.h"
  1228. _main()             /* main(n) */
  1229. {                   /* { */
  1230.     BEGIN;
  1231.     LPUSH(0);       /* print fact(n); */
  1232.     CALL(fact);
  1233.     PRINT;
  1234.     SPUSH("\en");    /* print "\en"; */
  1235.     PRINT;
  1236.     END;            /* } */
  1237. }
  1238. .cE
  1239. .cB
  1240. fact()              /* fact(n) */
  1241. {
  1242.     BEGIN;
  1243.     LPUSH(0);       /* if ( n == "0" ) */
  1244.     SPUSH("0");
  1245.     EQ;
  1246.     BRF(iflabel0);
  1247.     SPUSH("1");     /* return "1"; */
  1248.     RETURN;
  1249. iflabel0: ;
  1250.     LPUSH(0);       /* return n * fact(n - "1"); */
  1251.     LPUSH(0);
  1252.     SPUSH("1");
  1253.     SUB;
  1254.     CALL(fact);
  1255.     MUL;
  1256.     RETURN;
  1257.     END;            /* } */
  1258. }
  1259. .cE
  1260. .LP
  1261. .NH 2
  1262. .iH Augmenting grammar to dump stack code
  1263. .PP
  1264. In order to generate code, we must track the offset of local
  1265. variables.  To do so, we add a field, \f(CWoffset\fP, to our symbol
  1266. table record:
  1267. .cB
  1268. typedef struct symrec {
  1269.     char * symbol;
  1270.     struct symrec *next, *prev, **head, *scope;
  1271.     unsigned hash;
  1272.     int token;  /* either FUNC or VAR */
  1273.     int level;  /* either LOCAL, GLOBAL, PARAMETER */
  1274.     int offset; /* offset from sp on the stack */
  1275.                 /* locals are negative offsets, param is 0 */
  1276.     } Sym, *SymPtr;
  1277. .cE
  1278. .PP
  1279. We begin modifying our grammar by making a global variable that tracks
  1280. the offset of local variables and defining a variable to track label
  1281. numbers:
  1282. .cB
  1283. static int current_local_var_offset, LabelNum=0;
  1284. .cE
  1285. .PP
  1286. Because the translation of all programs must include the \fIsc\fP
  1287. stack machine definitions, we add a \f(CWprintf\fP to rule \f(CWp\fP:
  1288. .cB
  1289. p       :   <<Sym *p; printf("#include \e"sc.h\e"\en"); >>
  1290.             ( func | "var" def[&globals, GLOBAL] ";" )*
  1291.             <<  p = zzs_rmscope(&globals); >>
  1292.             "@"
  1293.         ;
  1294. .cE
  1295. .PP
  1296. In order to generate the variable definition macros and update the
  1297. symbol table, we modify rule \f(CWdef\fP as follows:
  1298. .cB
  1299. def[Sym **scope, int level]
  1300.         :   <<Sym *var;>>
  1301.             (   WORD
  1302.                 <<zzs_scope($scope);
  1303.                   var = zzs_newadd($1.text);
  1304.                   var->level = $level;
  1305.                   var->token = VAR;
  1306.                   var->offset = current_local_var_offset++;
  1307.                   switch(var->level) {
  1308.                         case GLOBAL: printf("SCVAR %s;\en", $1.text); break;
  1309.                         case  LOCAL : printf("\etLOCAL;\en"); break;
  1310.                   }
  1311.                 >>
  1312.             |   VAR
  1313.                 <<var = zzs_get($1.text);
  1314.                   if ( $level != var->level )
  1315.                   {
  1316.                     zzs_scope($scope);
  1317.                     var = zzs_newadd($1.text);
  1318.                     var->level = $level;
  1319.                     var->token = VAR;
  1320.                     var->offset = current_local_var_offset++;
  1321.  
  1322.                     switch(var-> level) {
  1323.                         case GLOBAL: printf("\etSCVAR %s;\en",$1.text);break;
  1324.                         case  LOCAL : printf("\etLOCAL;\en"); break;
  1325.                     }
  1326.                   }
  1327.                   else printf("redefined variable ignored: %s\en",$1.text);
  1328.                 >>
  1329.             )
  1330.         ;
  1331. .cE
  1332. .PP
  1333. The function definition rule must now dump a function template to
  1334. \f(CWstdout\fP and generate the \f(CWBEGIN\fP and \f(CWEND\fP macros.
  1335. \f(CWfunc\fP must also update \f(CWcurrent_local_var_offset\fP.  Note
  1336. that the code to dump symbols is gone.
  1337. .cB
  1338. func :  <<Sym *locals=NULL, *var, *p; current_local_var_offset =0;>>
  1339.             WORD
  1340.             <<zzs_scope(&globals);
  1341.               var = zzs_newadd($1.text);
  1342.               var->level = GLOBAL;
  1343.               var->token = FUNC;
  1344.  
  1345.               if (strcmp("main",$1.text)) { printf("%s()\en",$1.text); }
  1346.               else printf("_main()\en");
  1347.             >>
  1348.             "\e(" (  def[&locals, PARAMETER]
  1349.                  |  <<current_local_var_offset = 1;>>
  1350.                  )
  1351.             "\e)"
  1352.             "\e{" << printf("{\en\etBEGIN;\en"); >>
  1353.                 ( "var" def[&locals, LOCAL] ";" )*
  1354.                 ( statement )*
  1355.             "\e}" << printf("\etEND;\en}\en"); >>
  1356.             <<  p = zzs_rmscope(&locals); >>
  1357.         ;
  1358. .cE
  1359. .PP
  1360. Statements are easy to handle since \f(CWexpr\fP generates most of the
  1361. code.
  1362. .cB
  1363. statement : <<int n;>>
  1364.             expr ";"            <<printf("\etPOP;\en");>>
  1365.         |   "\e{" ( statement )* "\e}"
  1366.         |   "if" "\e(" expr "\e)" << n = LabelNum++;
  1367.                                    printf("\etBRF(iflabel%d);\en",n); >>
  1368.                 statement       << printf("iflabel%d: ;\en",n); >>
  1369.             {"else" statement}
  1370.         |
  1371.             "while"             << n = LabelNum++;
  1372.                                    printf("wbegin%d: ;\en", n); >>
  1373.             "\e(" expr "\e)"      << printf("\etBRF(wend%d);\en",n); >>
  1374.             statement           << printf("\etBR(wbegin%d);\en", n); >>
  1375.                                 << printf("wend%d: ;\en",n); >>
  1376.                                 << n++; >>
  1377.         |   "return" expr ";"   << printf("\etRETURN;\en"); >>
  1378.         |   "print" expr ";"    << printf("\etPRINT;\en"); >>
  1379.         ;
  1380. .cE
  1381. .NH 2
  1382. .iH Full translator
  1383. .PP
  1384. The following grammar accepts programs in \fIsc\fP and translates them
  1385. into stack code.
  1386. .cB
  1387. #header <<#include "sym.h"
  1388.           #include "charbuf.h"
  1389.         >>
  1390.  
  1391. #token "[\et\e ]+"  << zzskip(); >>                /* Ignore White */
  1392. #token "\en"       << zzline++; zzskip(); >>
  1393. #token STRING     "\e"(~[\e0-\e0x1f\e"\e\e]|(\e\e~[\e0-\e0x1f]))*\e"" <<;>>
  1394.  
  1395. <<
  1396. #define HashTableSize       999
  1397. #define StringTableSize     5000
  1398. #define GLOBAL              0
  1399. #define PARAMETER           1
  1400. #define LOCAL               2
  1401.  
  1402. static Sym *globals = NULL; /* global scope for symbols */
  1403. static int current_local_var_offset, LabelNum=0;
  1404. .cE
  1405. .cB
  1406. main()
  1407. {
  1408.     zzs_init(HashTableSize, StringTableSize);
  1409.     ANTLR(p(), stdin);
  1410. }
  1411.  
  1412. pScope(p)
  1413. Sym *p;
  1414. {
  1415.     for (; p!=NULL; p=p->scope)
  1416.     {
  1417.         printf("\etlevel %d | %-12s | %-15s\en",
  1418.             p->level,
  1419.             zztokens[p->token],
  1420.             p->symbol);
  1421.     }
  1422. }
  1423. >>
  1424. .cE
  1425. .cB
  1426. p       :   <<Sym *p; printf("#include \e"sc.h\e"\en"); >>
  1427.             ( func | "var" def[&globals, GLOBAL] ";" )*
  1428.             <<  p = zzs_rmscope(&globals); >>
  1429.             "@"
  1430.         ;
  1431.  
  1432. def[Sym **scope, int level]
  1433.         :   <<Sym *var;>>
  1434.             (   WORD
  1435.                 <<zzs_scope($scope);
  1436.                   var = zzs_newadd($1.text);
  1437.                   var->level = $level;
  1438.                   var->token = VAR;
  1439.                   var->offset = current_local_var_offset++;
  1440.                   switch(var->level) {
  1441.                         case  GLOBAL: printf("SCVAR %s;\en", $1.text); break;
  1442.                         case  LOCAL : printf("\etLOCAL;\en"); break;
  1443.                   }
  1444.                 >>
  1445.             |   VAR
  1446.                 <<var = zzs_get($1.text);
  1447.                   if ( $level != var->level )
  1448.                   {
  1449.                     zzs_scope($scope);
  1450.                     var = zzs_newadd($1.text);
  1451.                     var->level = $level;
  1452.                     var->token = VAR;
  1453.                     var->offset = current_local_var_offset++;
  1454.  
  1455.                     switch(var-> level) {
  1456.                         case  GLOBAL: printf("\etSCVAR %s;\en", $1.text); break;
  1457.                         case  LOCAL : printf("\etLOCAL;\en"); break;
  1458.                     }
  1459.                   }
  1460.                   else printf("redefined variable ignored: %s\en", $1.text);
  1461.                 >>
  1462.             )
  1463.         ;
  1464. .cE
  1465. .cB
  1466. func    :   <<Sym *locals=NULL, *var, *p; current_local_var_offset = 0;>>
  1467.             WORD
  1468.             <<zzs_scope(&globals);
  1469.               var = zzs_newadd($1.text);
  1470.               var->level = GLOBAL;
  1471.               var->token = FUNC;
  1472.  
  1473.               if (strcmp("main",$1.text)) { printf("%s()\en",$1.text); }
  1474.               else printf("_main()\en");
  1475.             >>
  1476.             "\e(" (  def[&locals, PARAMETER]
  1477.                  |  <<current_local_var_offset = 1;>>
  1478.                  )
  1479.             "\e)"
  1480.             "\e{" << printf("{\en\etBEGIN;\en"); >>
  1481.                 ( "var" def[&locals, LOCAL] ";" )*
  1482.                 ( statement )*
  1483.             "\e}" << printf("\etEND;\en}\en"); >>
  1484.             <<  p = zzs_rmscope(&locals); >>
  1485.         ;
  1486.  
  1487. statement : <<int n;>>
  1488.             expr ";"            <<printf("\etPOP;\en");>>
  1489.         |   "\e{" ( statement )* "\e}"
  1490.         |   "if" "\e(" expr "\e)" << n = LabelNum++;
  1491.                                    printf("\etBRF(iflabel%d);\en",n); >> 
  1492.                 statement       << printf("iflabel%d: ;\en",n); >>
  1493.             {"else" statement}
  1494.         |   
  1495.             "while"             << n = LabelNum++;
  1496.                                    printf("wbegin%d: ;\en", n); >>
  1497.             "\e(" expr "\e)"      << printf("\etBRF(wend%d);\en",n); >>
  1498.             statement           << printf("\etBR(wbegin%d);\en", n); >>
  1499.                                 << printf("wend%d: ;\en",n); >>
  1500.                                 << n++; >>
  1501.         |   "return" expr ";"   << printf("\etRETURN;\en"); >>
  1502.         |   "print" expr ";"    << printf("\etPRINT;\en"); >>
  1503.         ;
  1504. .cE
  1505. .cB
  1506. expr    :   <<Sym *s;>>
  1507.             VAR "=" expr        << printf("\etDUP;\en"); >>
  1508.             <<s = zzs_get($1.text);
  1509.               if ( s->level != GLOBAL )
  1510.                 printf("\etLSTORE(%d);\en", s->offset);
  1511.               else printf("\etSTORE(%s);\en", s->symbol);
  1512.             >>
  1513.         |   expr0
  1514.         ;
  1515.  
  1516. expr0   :   <<char *op;>>
  1517.             expr1 ( (   "==" <<op="EQ";>>
  1518.                     |   "!=" <<op="NEQ";>>
  1519.                     )
  1520.                     expr1
  1521.                     <<printf("\et%s;\en", op);>>
  1522.                   )*
  1523.         ;
  1524.  
  1525. expr1   :   <<char *op;>>
  1526.             expr2 ( (   "\e+" <<op="ADD";>>
  1527.                     |   "\e-" <<op="SUB";>>
  1528.                     )
  1529.                     expr2
  1530.                     <<printf("\et%s;\en", op);>>
  1531.                   )*
  1532.         ;
  1533.  
  1534. expr2   :   <<char *op;>>
  1535.             expr3 ( (   "\e*" <<op="MUL";>>
  1536.                     |   "/"  <<op="DIV";>>
  1537.                     )
  1538.                     expr3
  1539.                     <<printf("\et%s;\en", op);>>
  1540.                   )*
  1541.         ;
  1542. .cE
  1543. .cB
  1544. expr3   :   <<char *op=NULL;>>
  1545.             {"\e-" <<op="NEG";>>} expr4
  1546.             <<if ( op!=NULL ) printf("\et%s;\en", op);>>
  1547.         ;
  1548.  
  1549. expr4   :   <<Sym *s; int arg;>>
  1550.             STRING   << printf("\etSPUSH(%s);\en", $1.text); >>
  1551.         |   VAR     << s = zzs_get($1.text);
  1552.                        if ( s->level != GLOBAL )
  1553.                             printf("\etLPUSH(%d);\en", s->offset);
  1554.                        else printf("\etPUSH(%s);\en", s->symbol);
  1555.                     >>
  1556.         |   (   FUNC    <<$0=$1;>>
  1557.             |   WORD    <<$0=$1;>>
  1558.             )
  1559.             "\e(" { <<arg=0;>> expr <<arg=1;>> } "\e)"
  1560.             <<if ( !arg ) printf("\etSPUSH(\e"\e");\en");
  1561.               printf("\etCALL(%s);\en", $1.text);>>
  1562.         |   "\e(" expr "\e)"
  1563.     ;
  1564.  
  1565. #token WORD "[a-zA-Z]+"
  1566.     <<{
  1567.         Sym *p = zzs_get(zzlextext);
  1568.         if ( p != NULL ) NLA = p->token;
  1569.     }>>
  1570. .cE
  1571. .NH 2
  1572. .iH Makefile for Full Translator
  1573. .PP
  1574. The makefile is no different from the one used for the symbol table
  1575. management version of the tutorial except that we need to change the
  1576. \f(CWGRM\fP make variable as follows:
  1577. .cB
  1578. GRM=tut3
  1579. .cE
  1580. .LP
  1581. which implies that \f(CWtut3.g\fP is the file containing the third
  1582. revision of our \fIsc\fP translator.
  1583. .NH 2
  1584. .iH Use of translator
  1585. .PP
  1586. Once the translator has been made using the makefile, it is ready to
  1587. translate \fIsc\fP programs.  To translate and execute the factorial
  1588. example from above, we execute the following:
  1589. .cB
  1590. tut3 < fact.c > temp.c
  1591. .cE
  1592. where \f(CWfact.c\fP is the file containing the factorial code.
  1593. \f(CWtemp.c\fP will contain the translated program.  It is valid C
  1594. code because it is nothing more than a bunch of macro invocations (the
  1595. macros are defined in \f(CWsc.h\fP).  We can compile \f(CWtemp.c\fP
  1596. like any other C program:
  1597. .cB
  1598. cc temp.c
  1599. .cE
  1600. .LP
  1601. To execute the program, we type:
  1602. .cB
  1603. a.out \fIn\fP
  1604. .cE
  1605. .LP
  1606. where \fIn\fP is the number you want the factorial of.  Typing:
  1607. .cB
  1608. a.out 8
  1609. .cE
  1610. .LP
  1611. yields:
  1612. .cB
  1613. 40320.000000
  1614. .cE
  1615. .NH 2
  1616. .iH Stack code macros\ \(em \f(CWsc.h\fP
  1617. .PP
  1618. The following file is included by any C program using the stack code
  1619. instructions outlined above.
  1620. .cB
  1621. /* sc.h -- string C stack machine macros
  1622.  *
  1623.  * For use with PCCTS advanced tutorial version 1.0x
  1624.  */
  1625. #include <stdio.h>
  1626. #include <ctype.h>
  1627. #include <math.h>
  1628.  
  1629. /*
  1630.  * The function invocation stack looks like:
  1631.  *
  1632.  *  |    .        |
  1633.  *  |    .        |
  1634.  *  |    arg        |    fp + 0        arg is "" if none specified
  1635.  *  | 1st local    |    fp - 1
  1636.  *  | 2nd local    |    fp - 2
  1637.  *  |    ...        |
  1638.  *  |    .        |
  1639.  *  |    .        |
  1640.  */
  1641. .cE
  1642. .cB
  1643. #define STR_SIZE        100
  1644. #define STK_SIZE        200
  1645. /* define stack */
  1646. typedef struct { char text[STR_SIZE]; } SCVAR;
  1647. static SCVAR stack[STK_SIZE];
  1648. static int sp = STK_SIZE, fp;
  1649.  
  1650. /* number begins with number or '.' followed by number.  All numbers
  1651.  * are converted to floats before comparison.
  1652.  */
  1653. #define SCnumber(a)    (isdigit(a[0]) || (a[0]=='.' && isdigit(a[1])))
  1654. .cE
  1655. .cB
  1656. #define TOS            stack[sp].text
  1657. #define NTOS        stack[sp+1].text
  1658. #define TOSTRUE        ((strcmp(TOS, "true")==0)||(strcmp(TOS, "1")==0)        \e
  1659.                     ||(SCnumber(TOS)&&atof(TOS)==1.0) )
  1660. #define TOSFALSE    ((strcmp(TOS, "false")==0)||(strcmp(TOS, "0")==0)        \e
  1661.                     ||(SCnumber(TOS)&&atof(TOS)==0.0) )
  1662.  
  1663. #define PUSH(a)        {if ( sp==0 ) {fprintf(stderr, "stk ovf!\en"); exit(-1);} \e
  1664.                     strcpy(stack[--sp].text, (a).text);}
  1665.  
  1666. #define SPUSH(a)    {if ( sp==0 ) {fprintf(stderr, "stk ovf!\en"); exit(-1);} \e
  1667.                     strcpy(stack[--sp].text, a);}
  1668.  
  1669. #define LPUSH(a)    {if ( sp==0 ) {fprintf(stderr, "stk ovf!\en"); exit(-1);} \e
  1670.                     stack[--sp] = stack[fp-a];}
  1671. .cE
  1672. .cB
  1673. #define CALL(f)        {f();}
  1674.  
  1675. #define POP            stack[sp++]
  1676.  
  1677. #define LOCAL        {if ( sp==0 ) {fprintf(stderr, "stk ovf!\en"); exit(-1);} \e
  1678.                     stack[--sp].text[0] = '\e0';}
  1679. .cE
  1680. .cB
  1681. #define BRF(lab)    if ( TOSFALSE ) {POP; goto lab;} else POP;
  1682. #define BRT(lab)    if ( TOSTRUE ) {POP; goto lab;} else POP;
  1683. #define BR(lab)        goto lab
  1684.  
  1685. #define PRINT        printf("%s", POP.text)
  1686.  
  1687. #define RETURN        {strcpy(stack[fp].text, TOS); END; return;}
  1688.  
  1689. #define STORE(v)    {v = POP;}
  1690. #define LSTORE(off)    {stack[fp-off] = POP;}
  1691. .cE
  1692. .cB
  1693. /* operators */
  1694.  
  1695. #define EQ            {char *a,*b; float c,d;                                    \e
  1696.                     a = POP.text; b = POP.text;                                \e
  1697.                     if ( SCnumber(a) && SCnumber(b) ) {                        \e
  1698.                         c=atof(a); d=atof(b);                                \e
  1699.                         if ( c == d ) {SPUSH("true");}                        \e
  1700.                         else SPUSH("false");                                \e
  1701.                     }                                                        \e
  1702.                     else if ( strcmp(a, b)==0 ) {SPUSH("true");}            \e
  1703.                          else SPUSH("false");}
  1704. #define NEQ            {SCVAR a,b; float c,d;                                    \e
  1705.                     a = POP.text; b = POP.text;                                \e
  1706.                     if ( SCnumber(a) && SCnumber(b) ) {                        \e
  1707.                         c=atof(a); d=atof(b);                                \e
  1708.                         if ( c != d ) {SPUSH("true");}                        \e
  1709.                         else SPUSH("false");                                \e
  1710.                     }                                                        \e
  1711.                     else if ( strcmp(a, b)!=0 ) {SPUSH("true");}            \e
  1712.                          else SPUSH("false");}
  1713. #define ADD            {SCVAR c; float a,b;                                    \e
  1714.                     if ( !SCnumber(NTOS) || !SCnumber(TOS) ) {                 \e
  1715.                         strncat(NTOS, TOS, STR_SIZE - strlen(NTOS));        \e
  1716.                         sp++;                                                \e
  1717.                     } else {                                                \e
  1718.                         a=atof(POP.text); b=atof(POP.text);                    \e
  1719.                         sprintf(c.text, "%f", a+b); PUSH(c);                \e
  1720.                     }}
  1721. #define SUB            {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \e
  1722.                     sprintf(c.text, "%f", b-a); PUSH(c);}
  1723. #define MUL            {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \e
  1724.                     sprintf(c.text, "%f", a*b); PUSH(c);}
  1725. #define DIV            {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \e
  1726.                     sprintf(c.text, "%f", b/a); PUSH(c);}
  1727. #define NEG            {SCVAR c; float a; a=atof(POP.text); \e
  1728.                     sprintf(c.text, "%f", -a); PUSH(c);}
  1729. #define DUP            {if ( sp==0 ) {fprintf(stderr, "stk ovf!\en"); exit(-1);} \e
  1730.                     stack[sp-1] = stack[sp]; --sp;}
  1731. .cE
  1732. .cB
  1733. #define BEGIN        int save_fp = fp; fp = sp
  1734. #define END            sp = fp; fp = save_fp;
  1735.  
  1736. main(argc, argv)
  1737. int argc;
  1738. char *argv[];
  1739. {
  1740.     if ( argc == 2 ) {SPUSH(argv[1]);}
  1741.     else SPUSH("");
  1742.     CALL(_main);
  1743.     POP;
  1744. }
  1745. .cE
  1746. .NH
  1747. .iH Intermediate form construction
  1748. .PP
  1749. This section describes how trees can be used as an intermediate form
  1750. of the \fIsc\fP source program and how our \f(CWtut2.g\fP symbol table
  1751. management example can be modified to construct these trees.  Example
  1752. tree constructions are given as well as the complete source.
  1753.  
  1754.     Note that this section and the code generation section essentially
  1755. duplicate the translation achieved in the previous section on stack
  1756. code.  We arrive at the solution from a different angle, however.
  1757. This method is much more general and would be used for \*Qreal\*U
  1758. grammars.
  1759. .NH 2
  1760. .iH Tree Construction
  1761. .PP
  1762. To construct an intermediate form (IF) representation of an \fIsc\fP
  1763. program, we will construct trees using the abstract syntax tree (AST)
  1764. mechanism provided with PCCTS.  PCCTS supports an automatic and an
  1765. explicit tree construction mechanism; we will use both.  We will
  1766. augment the grammar that has the symbol table management actions\ \(em
  1767. \f(CWtut2.g\fP.
  1768. .PP
  1769. In order to use the AST mechanism within PCCTS, we must do the
  1770. following:
  1771. .IP \(bu
  1772. Define the AST fields, \f(CWAST_FIELDS\fP, needed by the user.
  1773. .IP \(bu
  1774. Define the default AST node constructor, \f(CWzzcr_ast()\fP, that
  1775. converts from a lexeme to an AST node.
  1776. .IP \(bu
  1777. Define an explicit AST node constructor\ \(em \f(CWzzmk_ast()\fP
  1778. (because we use the explicit tree constructor mechanism also).
  1779. .PP
  1780. Our tree nodes will contain a token number to identify the node.  This
  1781. token number can also be a value for which there is no corresponding
  1782. lexical item (e.g. a function call may have a node called
  1783. \f(CWDefineVar\fP).  If the token indicates that the node represents a
  1784. variable or function, we must have information as to its level, offset
  1785. from the frame pointer (if a local or parameter) and the string
  1786. representing the name of the item.  This information can all be held
  1787. via:
  1788. .cB
  1789. #define AST_FIELDS int token, level, offset; char str[D_TextSize];
  1790. .cE
  1791. .LP
  1792. which will be added to the \f(CW#header\fP PCCTS pseudo-op action.
  1793. Note that \f(CWD_TextSize\fP is defined in \f(CWcharbuf\fP.h.
  1794. .PP
  1795. To tell PCCTS how it should build AST nodes for use with the automatic
  1796. tree construction mechanism, we define the following macro in the
  1797. \f(CW#header\fP action:
  1798. .cB
  1799. #define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
  1800. .cE
  1801. .LP
  1802. which merely calls a function we define as follows:
  1803. .cB
  1804. create_ast(ast,attr,tok,text)
  1805. AST *ast;
  1806. Attrib *attr;
  1807. int tok;
  1808. char *text;
  1809. {
  1810.     Sym *s;
  1811.  
  1812.     ast->token = tok;
  1813.     if ( tok == VAR )
  1814.     {
  1815.         s = zzs_get(text);
  1816.         ast->level = s->level;
  1817.         ast->offset = s->offset;
  1818.     }
  1819.     if ( tok == STRING || tok == VAR || tok == FUNC ) strcpy(ast->str, text);
  1820. }
  1821. .cE
  1822. .LP
  1823. Because of the symbol table lookup etc... we make the node constructor
  1824. a function rather than have the code replicated at each invocation of
  1825. the \f(CWzzcr_ast\fP macro.
  1826. .PP
  1827. When we explicitly construct trees, the automatic node constructor is
  1828. generally disabled and we must explicitly call a function to create an
  1829. AST node:
  1830. .cB
  1831. AST *
  1832. zzmk_ast(node, token, str)
  1833. AST *node;
  1834. int token;
  1835. char *str;
  1836. {
  1837.     Sym *s;
  1838.  
  1839.     node->token = token;
  1840.     if ( token == VAR )
  1841.     {
  1842.         s = zzs_get(str);
  1843.         node->level = s->level;
  1844.         node->offset = s->offset;
  1845.     }
  1846.     if ( tok == STRING || tok == VAR || tok == FUNC )
  1847.         strcpy(node->str, str);
  1848.     return node;
  1849. }
  1850. .cE
  1851. This function will be invoked when we have a grammar action with a
  1852. reference of the form \f(CW#[\fItoken, string\fP]\fR.
  1853. .PP
  1854. In order to print out the trees that we have defined, let us define a
  1855. simple function to do a preorder, lisp-like walk of our trees:
  1856. .cB
  1857. lisp(tree)
  1858. AST *tree;
  1859. {
  1860.     while ( tree!= NULL )
  1861.     {
  1862.         if ( tree->down != NULL ) printf(" (");
  1863.         if ( tree->token == STRING ||
  1864.              tree->token == VAR ||
  1865.              tree->token == FUNC ) printf(" %s", tree->str);
  1866.         else printf(" %s", zztokens[tree->token]);
  1867.         lisp(tree->down);
  1868.         if ( tree->down != NULL ) printf(" )");
  1869.         tree = tree->right;
  1870.     }
  1871. }
  1872. .cE
  1873. .PP
  1874. PCCTS automatically assumes that all rules will produce trees and that
  1875. all terminals within rules will result in nodes added to the current
  1876. tree.  In the case of rules \f(CWp\fP, \f(CWexpr4\fP,
  1877. \f(CWstatement\fP and \f(CWfunc\fP, this is not true.  We will
  1878. explicitly handle the trees within these rules.  Therefore, we append
  1879. a \f(CW!\fP after the definition of these rules.  We need to decide
  1880. how each \fIsc\fP construct will be translated to a subtree and when
  1881. we will pass these trees off to the code generator.  We will collect
  1882. all subtrees within a function and then, just before we remove the
  1883. symbols for that function, we will pass this tree off to \f(CWlisp\fP
  1884. to be printed; we will pass it off to the code generator when we
  1885. define it in the next section.  After it has been printed, the
  1886. function trees will be destroyed.  For global variable definitions, we
  1887. will pass each one individually off to
  1888. \f(CWlisp\fP and then destroy the tree.
  1889. .PP
  1890. Before modifying the rules of the grammar, we must define labels for a
  1891. number of regular expressions so that the token value of that
  1892. expression can be referenced from within an action.  We also define
  1893. labels for tokens which do not exist physically in a program, but are
  1894. needed for code generation.
  1895. .cB
  1896. /* Not actual terminals, just node identifiers */
  1897. #token DefineFunc
  1898. #token SLIST
  1899. .cE
  1900. .cB
  1901. /* Define tokens for code generation */
  1902. #token DefineVar    "var"
  1903. #token Mul          "\*"
  1904. #token Div          "/"
  1905. #token Add          "\+"
  1906. #token Sub          "\-"
  1907. #token Equal        "=="
  1908. #token NotEqual     "!="
  1909. #token If           "if"
  1910. #token While        "while"
  1911. #token Return       "return"
  1912. #token Print        "print"
  1913. #token Assign       "="
  1914. .cE
  1915. .PP
  1916. All PCCTS grammars that use the AST mechanism need to pass the address
  1917. of a \f(CWNULL\fP pointer to the starting rule.
  1918. .cB
  1919. main()
  1920. {
  1921.     AST *root=NULL;
  1922.  
  1923.     zzs_init(HashTableSize, StringTableSize);
  1924.     ANTLR(p(&root), stdin);
  1925. }
  1926. .cE
  1927. .PP
  1928. Rule \f(CWp\fP is modified as follows:
  1929. .cB
  1930. p!      :   <<Sym *p; AST *v;>>
  1931.             (   func
  1932.             |   "var" def[&globals, GLOBAL] ";"
  1933.                 <<v = #(#[DefineVar], #2);
  1934.                   lisp(v); printf("\en"); zzfree_ast(v);
  1935.                 >>
  1936.             )*
  1937.             <<p = zzs_rmscope(&globals);>>
  1938.             "@"
  1939.         ;
  1940. .cE
  1941. .LP
  1942. The \f(CW#[DefineVar]\fP reference calls our \f(CWzzmk_ast\fP macro
  1943. to create an AST node whose token is set to \f(CWDefineVar\fP.  The
  1944. reference to \f(CW#(#[DefineVar], #2)\fP is a tree constructor
  1945. which makes the \f(CWDefineVar\fP node the parent of the tree returned
  1946. by rule \f(CWdef\fP\ \(em \f(CW#2\fP.  In general, the tree
  1947. constructor has the form:
  1948. .cB
  1949. #( \fIroot\fP, \fIsibling1\fP, \fIsibling2\fP, ..., \fIsiblingN\fP )
  1950. .cE
  1951. .LP
  1952. where any \f(CWNULL\fP pointer terminates the list except for the root
  1953. pointer. \f(CW#2\fP refers to the second AST node or tree within an
  1954. alternative\ \(em \f(CWdef\fP in our case.  Rule \f(CWdef\fP itself
  1955. does not change because PCCTS automatically creates a node for the
  1956. \f(CWWORD\fP or \f(CWVAR\fP and passes it back to the invoking rule.
  1957. .PP
  1958. Trees for functions are constructed in the following form:
  1959. .cB
  1960.      DefineFunc
  1961.          |
  1962.          v
  1963.         FUNC -> DefineVar -> DefineVar -> SLIST
  1964.                     |            |          |
  1965.                     v            |          v
  1966.               optional_arg       |        stat1 -> ... > statn
  1967.                                  v
  1968.                                local1 -> ... -> localn
  1969. .cE
  1970. .LP
  1971. where \f(CWDefineFunc\fP and \f(CWDefineVar\fP are dummy tokens used
  1972. only in trees (as opposed to the grammar).  Rule \f(CWfunc\fP is
  1973. modified to build these trees:
  1974. .cB
  1975. func!  :  <<Sym *locals=NULL, *var, *p; AST *f,*parm=NULL,*v=NULL,*s=NULL;
  1976.               current_local_var_offset = 0;>>
  1977.             WORD
  1978.             <<zzs_scope(&globals);
  1979.               var = zzs_newadd($1.text);
  1980.               var->level = GLOBAL;
  1981.               var->token = FUNC;
  1982.             >>
  1983.             "\e(" (  def[&locals, PARAMETER] <<parm=#1;>>
  1984.                  |  <<current_local_var_offset = 1;>>
  1985.                  )
  1986.             "\e)"
  1987.             "\e{"
  1988.                 ( "var" def[&locals, LOCAL]
  1989.                   <<if ( v==NULL ) v = #2; else v = #(NULL,v,#2);>>
  1990.                   ";"
  1991.                 )*
  1992.                 ( statement
  1993.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  1994.                 )*
  1995.             "\e}"
  1996.             <<s = #(#[SLIST], s);
  1997.               v = #(#[DefineVar], v);
  1998.               parm = #(#[DefineVar], parm);
  1999.               f = #(#[DefineFunc], #[FUNC,$1.text], parm, v, s);
  2000.               lisp(f); printf("\een"); zzfree_ast(f);
  2001.               p = zzs_rmscope(&locals);>>
  2002.         ;
  2003. .cE
  2004. .LP
  2005. Variable \f(CWparm\fP is set to the AST node created by \f(CWdef\fP
  2006. if a parameter is found else it is \f(CWNULL\fP.  Variable \f(CWv\fP
  2007. is used to maintain a list of local variables.  The tree constructor
  2008. .cB
  2009. v = #(NULL,v,#2);
  2010. .cE
  2011. .LP
  2012. says to make a new tree with no root and with siblings \f(CWv\fP and
  2013. \f(CW#2\fP\ \(em which effectively links \f(CW#2\fP to the end of the
  2014. current list of variables.  Variable \f(CWs\fP behaves in a similar
  2015. fashion.  After the list of variables and statements have been
  2016. accumulated, we add a dummy node (\f(CWDefineVar\fP, \f(CWSLIST\fP) as
  2017. a root to each list so that we get the structure given above.  To
  2018. examine the trees we have constructed, we make a call to \f(CWlisp\fP
  2019. and then destroy the tree.
  2020. .PP
  2021. Even though it is not necessary to do so, we will build trees for
  2022. \f(CWstatement\fP explicitly (in general, the automatic mechanism is
  2023. best for expressions with simple operator/operand relationships).
  2024. .cB
  2025. statement!: <<AST *s=NULL, *el=NULL;>>
  2026.             expr ";"                          <<#0 = #1;>>
  2027.         |   "\e{"
  2028.                 ( statement
  2029.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  2030.                 )*
  2031.             "\e}" <<#0 = #(#[SLIST], s);>>
  2032.         |   "if" "\e(" expr "\e)" statement
  2033.             {"else" statement <<el=#2;>>}     <<#0 = #(#[If], #3, #5,el);>>
  2034.         | "while" "\e(" expr "\e)" statement    <<#0 = #(#[While], #3,#5);>>
  2035.         | "return" expr ";"                   <<#0 = #(#[Return], #2);>>
  2036.         | "print" expr ";"                    <<#0 = #(#[Print], #2);>>
  2037.         ;
  2038. .cE
  2039. .LP
  2040. Many of the tokens in \f(CWstatement\fP are not included in the tree
  2041. because they are a notational convenience for humans or are used for
  2042. grouping purposes.  As before, we track lists of statements using the
  2043. tree constructor: \f(CW#(NULL,s,#1)\fP.
  2044. .PP
  2045. The last unusual rule is \f(CWexpr\fP:
  2046. .cB
  2047. expr4!  :   <<AST *f=NULL, *arg=NULL;>>
  2048.             STRING          <<#0 = #[STRING, $1.text];>>
  2049.         |   VAR             <<#0 = #[STRING, $1.text];>>
  2050.         |   (   FUNC        <<f  = #[FUNC, $1.text];>>
  2051.             |   WORD        <<f  = #[FUNC, $1.text];>>
  2052.             )
  2053.             "\e(" { expr <<arg=#1;>> } "\e)"
  2054.             <<#0 = #(f, arg);>>
  2055.         |   "\e(" expr "\e)"  <<#0 = #2;>>
  2056.         ;
  2057. .cE
  2058. .LP
  2059. Assigning a tree to \f(CW#0\fP makes that tree the return tree.
  2060. However, it should really only be used in rules that do not use the
  2061. automatic tree construction mechanism; i.e. there is a \f(CW! after\fP
  2062. the rule definition.  For a function call, we make a tree with a
  2063. \f(CWFUNC\fP node at the root and the optional argument as the child.
  2064. The third alternative merely returns what is computed by \f(CWexpr\fP;
  2065. the parenthesis are mechanism for syntactic precedence and add nothing
  2066. to the tree.  The tree structure itself embodies the precedence.
  2067. .PP
  2068. The only other required modifications to the grammar are to indicate
  2069. which tokens are operators (subtree roots) and which are operands in
  2070. the expression rules.  To indicate that a token is to be made a
  2071. subtree root, we append a \f(CW^\fP.  All other tokens are considered
  2072. operands (children).  Appending a token with \f(CW!\fP indicates that
  2073. it is not to be included in the tree.  For example, to make trees like:
  2074. .cB
  2075.         operator
  2076.             |
  2077.             v
  2078.           opnd1 -> opnd2
  2079. .cE
  2080. .LP
  2081. we modify the operators in \f(CWexpr\fP through \f(CWexpr3\fP in a
  2082. fashion similar to:
  2083. .cB
  2084. expr1   :   expr2 ( (   "\e+"^
  2085.                     |   "\e-"^
  2086.                     )
  2087.                     expr2
  2088.                   )*
  2089.         ;
  2090. .cE
  2091. .LP
  2092. and
  2093. .cB
  2094. expr3   :   { "\e-"^ } expr4
  2095.         ;
  2096. .cE
  2097. .NH 2
  2098. .iH Full Grammar to Construct Trees
  2099. .PP
  2100. The following grammar constructs AST's as an intermediate form (IF) of an
  2101. \fIsc\fP program and prints out the IF in lisp-like preorder.
  2102. .cB
  2103. #header <<#include "sym.h"
  2104.           #include "charbuf.h"
  2105.           #define AST_FIELDS int token, level, offset; char str[D_TextSize];
  2106.           #define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
  2107.           #define DONT_CARE         0
  2108.           #define SIDE_EFFECTS      1
  2109.           #define VALUE             2
  2110.         >>
  2111.  
  2112. #token "[\et\e ]+"    << zzskip(); >>                /* Ignore White */
  2113. #token "\en"         << zzline++; zzskip(); >>
  2114. #token STRING "\e"(~[\e0-\e0x1f\e"\e\e]|(\e\e~[\e0-\e0x1f]))*\e"" <<;>>
  2115.  
  2116. /* Not actual terminals, just node identifiers */
  2117. #token DefineFunc
  2118. #token SLIST
  2119. .cE
  2120. .cB
  2121. /* Define tokens for code generation */
  2122. #token DefineVar    "var"
  2123. #token Mul          "\e*"
  2124. #token Div          "/"
  2125. #token Add          "\e+"
  2126. #token Sub          "\e-"
  2127. #token Equal        "=="
  2128. #token NotEqual     "!="
  2129. #token If           "if"
  2130. #token While        "while"
  2131. #token Return       "return"
  2132. #token Print        "print"
  2133. #token Assign       "="
  2134.  
  2135. <<;>>
  2136.  
  2137. <<
  2138. #define HashTableSize       999
  2139. #define StringTableSize     5000
  2140. #define GLOBAL              0
  2141. #define PARAMETER           1
  2142. #define LOCAL               2
  2143. .cE
  2144. .cB
  2145. static Sym *globals = NULL; /* global scope for symbols */
  2146. static int current_local_var_offset=0;
  2147.  
  2148. create_ast(ast,attr,tok,text)
  2149. AST *ast;
  2150. Attrib *attr;
  2151. int tok;
  2152. char *text;
  2153. {
  2154.     Sym *s;
  2155.  
  2156.     ast->token = tok;
  2157.     if ( tok == VAR )
  2158.     {
  2159.         s = zzs_get(text);
  2160.         ast->level = s->level;
  2161.         ast->offset = s->offset;
  2162.     }
  2163.     if ( tok == STRING || tok == VAR || tok == FUNC ) strcpy(ast->str, text);
  2164. }
  2165. .cE
  2166. .cB
  2167. AST *
  2168. zzmk_ast(node, token, str)
  2169. AST *node;
  2170. int token;
  2171. char *str;
  2172. {
  2173.     Sym *s;
  2174.  
  2175.     node->token = token;
  2176.     if ( token == VAR )
  2177.     {
  2178.         s = zzs_get(str);
  2179.         node->level = s->level;
  2180.         node->offset = s->offset;
  2181.     }
  2182.     if ( token == STRING || token == VAR || token == FUNC )
  2183.         strcpy(node->str, str);
  2184.     return node;
  2185. }
  2186. .cE
  2187. .cB
  2188. lisp(tree)
  2189. AST *tree;
  2190. {
  2191.     while ( tree!= NULL )
  2192.     {
  2193.         if ( tree->down != NULL ) printf(" (");
  2194.         if ( tree->token == STRING ||
  2195.              tree->token == VAR ||
  2196.              tree->token == FUNC ) printf(" %s", tree->str);
  2197.         else printf(" %s", zztokens[tree->token]);
  2198.         lisp(tree->down);
  2199.         if ( tree->down != NULL ) printf(" )");
  2200.         tree = tree->right;
  2201.     }
  2202. }
  2203.  
  2204. main()
  2205. {
  2206.     AST *root=NULL;
  2207.  
  2208.     zzs_init(HashTableSize, StringTableSize);
  2209.     ANTLR(p(&root), stdin);
  2210. }
  2211. .cE
  2212. .cB
  2213. pScope(p)
  2214. Sym *p;
  2215. {
  2216.     for (; p!=NULL; p=p->scope)
  2217.     {
  2218.         printf("\etlevel %d | %-12s | %-15s\en",
  2219.             p->level,
  2220.             zztokens[p->token],
  2221.             p->symbol);
  2222.     }
  2223. }
  2224. >>
  2225.  
  2226. p!      :   <<Sym *p; AST *v;>>
  2227.             (   func
  2228.             |   "var" def[&globals, GLOBAL] ";"
  2229.                 <<v = #(#[DefineVar], #2);
  2230.                   gen(v,DONT_CARE); printf("\en"); zzfree_ast(v);
  2231.                 >>
  2232.             )*
  2233.             <<p = zzs_rmscope(&globals);>>
  2234.             "@"
  2235.         ;
  2236. .cE
  2237. .cB
  2238. def[Sym **scope, int level]
  2239.         :   <<Sym *var;>>
  2240.             (   WORD
  2241.                 <<zzs_scope($scope);
  2242.                   var = zzs_newadd($1.text);
  2243.                   var->level = $level;
  2244.                   var->token = VAR;
  2245.                   var->offset = current_local_var_offset++;
  2246.                 >>
  2247.             |   VAR
  2248.                 <<var = zzs_get($1.text);
  2249.                   if ( $level != var->level )
  2250.                   {
  2251.                     zzs_scope($scope);
  2252.                     var = zzs_newadd($1.text);
  2253.                     var->level = $level;
  2254.                     var->token = VAR;
  2255.                     var->offset = current_local_var_offset++;
  2256.                   }
  2257.                   else printf("redefined variable ignored: %s\en", $1.text);
  2258.                 >>
  2259.             )
  2260.         ;
  2261.  
  2262. func!   :   <<Sym *locals=NULL, *var, *p; AST *f,*parm=NULL,*v=NULL,*s=NULL;
  2263.               current_local_var_offset = 0;>>
  2264.             WORD
  2265.             <<zzs_scope(&globals);
  2266.               var = zzs_newadd($1.text);
  2267.               var->level = GLOBAL;
  2268.               var->token = FUNC;
  2269.             >>
  2270.             "\e(" (  def[&locals, PARAMETER] <<parm=#1;>>
  2271.                  |  <<current_local_var_offset = 1;>>
  2272.                  )
  2273.             "\e)"
  2274.             "\e{"
  2275.                 ( "var" def[&locals, LOCAL]
  2276.                   <<if ( v==NULL ) v = #2; else v = #(NULL,v,#2);>>
  2277.                   ";"
  2278.                 )*
  2279.                 ( statement
  2280.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  2281.                 )*
  2282.             "\e}"
  2283.             <<s = #(#[SLIST], s);
  2284.               v = #(#[DefineVar], v);
  2285.               parm = #(#[DefineVar], parm);
  2286.               f = #(#[DefineFunc], #[FUNC,$1.text], parm, v, s);
  2287.               gen(f,DONT_CARE); printf("\en"); zzfree_ast(f);
  2288.               p = zzs_rmscope(&locals);>>
  2289.         ;
  2290. .cE
  2291. .cB
  2292. statement!: <<AST *s=NULL, *el=NULL;>>
  2293.             expr ";"                            <<#0 = #1;>>
  2294.         |   "\e{"
  2295.                 ( statement
  2296.                   <<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
  2297.                 )*
  2298.             "\e}"                                <<#0 = #(#[SLIST], s);>>
  2299.         |   "if" "\e(" expr "\e)" statement
  2300.             {"else" statement <<el=#2;>>}       <<#0 = #(#[If], #3, #5, el);>>
  2301.         |   "while" "\e(" expr "\e)" statement    <<#0 = #(#[While], #3, #5);>>
  2302.         |   "return" expr ";"                   <<#0 = #(#[Return], #2);>>
  2303.         |   "print" expr ";"                    <<#0 = #(#[Print], #2);>>
  2304.         ;
  2305.  
  2306. expr    :   VAR "="^ expr
  2307.         |   expr0
  2308.         ;
  2309.  
  2310. expr0   :   expr1 ( (   "=="^
  2311.                     |   "!="^
  2312.                     )
  2313.                     expr1
  2314.                   )*
  2315.         ;
  2316.  
  2317. expr1   :   expr2 ( (   "\e+"^
  2318.                     |   "\e-"^
  2319.                     )
  2320.                     expr2
  2321.                   )*
  2322.         ;
  2323.  
  2324. expr2   :   expr3 ( (   "\e*"^
  2325.                     |   "/"^
  2326.                     )
  2327.                     expr3
  2328.                   )*
  2329.         ;
  2330. .cE
  2331. .cB
  2332. expr3   :   { "\e-"^ } expr4
  2333.         ;
  2334.  
  2335. expr4!  :   <<AST *f=NULL, *arg=NULL;>>
  2336.             STRING          <<#0 = #[STRING, $1.text];>>
  2337.         |   VAR             <<#0 = #[VAR, $1.text];>>
  2338.         |   (   FUNC        <<f  = #[FUNC, $1.text];>>
  2339.             |   WORD        <<f  = #[FUNC, $1.text];>>
  2340.             )
  2341.             "\e(" { expr <<arg=#1;>> } "\e)"
  2342.             <<#0 = #(f, arg);>>
  2343.         |   "\e(" expr "\e)"  <<#0 = #2;>>
  2344.         ;
  2345.  
  2346. #token WORD "[a-zA-Z]+"
  2347.     <<{
  2348.         Sym *p = zzs_get(LATEXT(1));
  2349.         if ( p != NULL ) NLA = p->token;
  2350.     }>>
  2351. .cE
  2352. .NH 2
  2353. .iH Example translations
  2354. .PP
  2355. To illustrate how functions get translated, consider the following
  2356. \fIsc\fP program:
  2357. .cB
  2358. var a;
  2359.  
  2360. main(n)
  2361. {
  2362.     var b;
  2363. }
  2364. .cE
  2365. .LP
  2366. Our translator would create trees represented by:
  2367. .cB
  2368.  ( DefineVar WORD )
  2369.  ( DefineFunc FUNC ( DefineVar WORD ) ( DefineVar WORD ) SLIST )
  2370. .cE
  2371. .LP
  2372. where \f(CWWORD\fP represents the variables found on the input
  2373. stream.  \f(CWSLIST\fP has no child because there were no statements
  2374. in the function.
  2375. .PP
  2376. Some example statement transformations follow.
  2377. .LP
  2378. \f(CWif\fP:
  2379. .cB
  2380. if ( b == "hello" ) print n;
  2381. .cE
  2382. .LP
  2383. translates to
  2384. .cB
  2385. ( If ( Equal b "hello" ) ( Print n ) )
  2386. .cE
  2387. .LP
  2388. \f(CWwhile\fP:
  2389. .cB
  2390. while ( i != "10" ) { print i; i = i+"1"; }
  2391. .cE
  2392. .LP
  2393. translates to
  2394. .cB
  2395. ( While ( NotEqual i "10" ) ( SLIST ( Print i ) ( = i ( Add i "1" ) ) ) )
  2396. .cE
  2397. .PP
  2398. Expressions have the operator at the root and the operands as
  2399. children.  For example,
  2400. .cB
  2401. i = a + "3" * "9" + f("jim");
  2402. .cE
  2403. .LP
  2404. would be translated to:
  2405. .cB
  2406. ( = i ( Add ( Add a ( Mul "3" "9" ) ) ( f "jim" ) ) )
  2407. .cE
  2408. .LP
  2409. which looks like:
  2410. .cB
  2411.         =
  2412.         |
  2413.         v
  2414.         i -> Add
  2415.               |
  2416.               v
  2417.              Add --------------> f
  2418.               |                  |
  2419.               v                  v
  2420.               a -> Mul         "jim"
  2421.                     |
  2422.                     v
  2423.                    "3" -> "9"
  2424. .cE
  2425. .NH
  2426. .iH  Code generation from intermediate form
  2427. .PP
  2428. To translate the intermediate form (IF) to the stack code described
  2429. above, we present the following simple little code generator.  We use
  2430. no devious C programming to make this fast or nifty because this
  2431. document concentrates on how PCCTS grammars are developed not on how
  2432. to write spectacular C code.
  2433. .NH 2
  2434. .iH Modification of tree construction grammar
  2435. .PP
  2436. To convert from the translator above that printed out trees in lisp
  2437. format, we add the following definitions needed as arguments to
  2438. \f(CWgen()\fP in the \f(CW#header\fP action.
  2439. .cB
  2440.           #define DONT_CARE         0
  2441.           #define SIDE_EFFECTS      1
  2442.           #define VALUE             2
  2443. .cE
  2444. .PP
  2445. Also, we replace all calls to \f(CWlisp(\fItree\fP)\fR with
  2446. \f(CWgen(\fItree\fP, DONT_CARE)\fP.
  2447. .NH 2
  2448. .iH Code generator
  2449. .PP
  2450. Function \f(CWgen()\fP presented below accepts an AST as an argument
  2451. and walks the tree generating output when necessary.  You will notice
  2452. all the header information needed by this file, \f(CWcode.c\fP.  This
  2453. illustrates one of the minor inconveniences of PCCTS.  Any C file that
  2454. needs to access PCCTS variables, rules, etc... must include all of the
  2455. things that PCCTS generates at the head of all PCCTS generated files.
  2456. .PP
  2457. The code generator accepts an evaluation mode argument so that it can
  2458. remove some unnecessary code.  For example,
  2459. .cB
  2460. main()
  2461. {
  2462.     "3" + f();
  2463. } 
  2464. f()
  2465. {}
  2466. .cE
  2467. .LP
  2468. would result in
  2469. .cB
  2470. #include "sc.h"
  2471. _main()
  2472. {
  2473.     BEGIN;
  2474.     CALL(f);
  2475.     POP;
  2476.     END;
  2477. }
  2478.  
  2479. f()
  2480. {
  2481.     BEGIN;
  2482.     END;
  2483. }
  2484. .cE
  2485. .LP
  2486. Code to push and add \f(CW"3"\fP was eliminated because it had no side
  2487. effects.  Only function calls have side effects in \fIsc\fP.
  2488. .cB
  2489. /*
  2490.  * Simple code generator for PCCTS 1.0x tutorial
  2491.  *
  2492.  * Terence Parr
  2493.  * Purdue University
  2494.  * Electrical Engineering
  2495.  * March 19, 1992
  2496.  */
  2497. #include <stdio.h>
  2498. #include "sym.h"
  2499. #include "charbuf.h"
  2500. #define AST_FIELDS int token, level, offset; char str[D_TextSize];
  2501. #define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
  2502. #include "antlr.h"
  2503. #include "ast.h"
  2504. #include "tokens.h"
  2505. #include "dlgdef.h"
  2506. #include "mode.h"
  2507. #define GLOBAL              0
  2508. #define PARAMETER           1
  2509. #define LOCAL               2
  2510. .cE
  2511. .cB
  2512. static int LabelNum=0, GenHeader=0;
  2513.  
  2514. #define DONT_CARE            0
  2515. #define SIDE_EFFECTS        1
  2516. #define VALUE                2
  2517. .cE
  2518. .cB
  2519. gen(t,emode)
  2520. AST *t;
  2521. int emode;    /* evaluation mode member { SIDE_EFFECTS, VALUE, DONT_CARE } */
  2522. {
  2523.     AST *func, *arg, *locals, *slist, *a, *opnd1, *opnd2, *lhs, *rhs;
  2524.     int n;
  2525. .cE
  2526. .cB
  2527.     if ( t == NULL ) return;
  2528.     if ( !GenHeader ) { printf("#include \e"sc.h\e"\en"); GenHeader=1; }
  2529.  
  2530.     switch ( t->token )
  2531.     {
  2532. .cE
  2533. .cB
  2534.     case DefineFunc :
  2535.         func = zzchild(t);
  2536.         arg = zzchild( zzsibling(func) );
  2537.         locals = zzchild( zzsibling( zzsibling(func) ) );
  2538.         slist = zzsibling( zzsibling( zzsibling(func) ) );
  2539.         if ( strcmp(func->str, "main") == 0 )
  2540.             printf("_%s()\en{\en\etBEGIN;\en", func->str);
  2541.         else
  2542.             printf("%s()\en{\en\etBEGIN;\en", func->str);
  2543.         for (a=locals; a!=NULL; a = zzsibling(a)) printf("\etLOCAL;\en");
  2544.         gen( slist, DONT_CARE );
  2545.         printf("\etEND;\en}\en");
  2546.         break;
  2547. .cE
  2548. .cB
  2549.     case SLIST :
  2550.         for (a=zzchild(t); a!=NULL; a = zzsibling(a))
  2551.         {
  2552.             gen( a, EvalMode(a->token) );
  2553.             if ( a->token == Assign ) printf("\etPOP;\en");
  2554.         }
  2555.         break;
  2556. .cE
  2557. .cB
  2558.     case DefineVar :
  2559.         printf("SCVAR %s;\en", zzchild(t)->str);
  2560.         break;
  2561. .cE
  2562. .cB
  2563.     case Mul :
  2564.     case Div :
  2565.     case Add :
  2566.     case Sub :
  2567.     case Equal :
  2568.     case NotEqual :
  2569.         opnd1 = zzchild(t);
  2570.         opnd2 = zzsibling( opnd1 );
  2571.         gen( opnd1, emode );
  2572.         gen( opnd2, emode );
  2573.         if ( emode == SIDE_EFFECTS ) break;
  2574.         switch ( t->token )
  2575.         {
  2576.         case Mul : printf("\etMUL;\en"); break;
  2577.         case Div : printf("\etDIV;\en"); break;
  2578.         case Add : printf("\etADD;\en"); break;
  2579.         case Sub : if ( opnd2==NULL ) printf("\etNEG;\en");
  2580.                    else printf("\etSUB;\en");
  2581.                    break;
  2582.         case Equal : printf("\etEQ;\en"); break;
  2583.         case NotEqual : printf("\etNEQ;\en"); break;
  2584.         }
  2585.         break;
  2586. .cE
  2587. .cB
  2588.     case If :
  2589.         a = zzchild(t);
  2590.         gen( a, VALUE );                /* gen code for expr */
  2591.         n = LabelNum++;
  2592.         printf("\etBRF(iflabel%d);\en", n);
  2593.         a = zzsibling(a);
  2594.         gen( a, EvalMode(a->token) );    /* gen code for statement */
  2595.         printf("iflabel%d: ;\en", n);
  2596.         break;
  2597. .cE
  2598. .cB
  2599.     case While :
  2600.         a = zzchild(t);
  2601.         n = LabelNum++;
  2602.         printf("wbegin%d: ;\en", n);
  2603.         gen( a, VALUE );                /* gen code for expr */
  2604.         printf("\etBRF(wend%d);\en", n);
  2605.         a = zzsibling(a);
  2606.         gen( a, EvalMode(a->token) );    /* gen code for statement */
  2607.         printf("\etBR(wbegin%d);\en", n);
  2608.         printf("wend%d: ;\en", n);
  2609.         break;
  2610. .cE
  2611. .cB
  2612.     case Return :
  2613.         gen( zzchild(t), VALUE );
  2614.         printf("\etRETURN;\en");
  2615.         break;
  2616. .cE
  2617. .cB
  2618.     case Print :
  2619.         gen( zzchild(t), VALUE );
  2620.         printf("\etPRINT;\en");
  2621.         break;
  2622. .cE
  2623. .cB
  2624.     case Assign :
  2625.         lhs = zzchild(t);
  2626.         rhs = zzsibling( lhs );
  2627.         gen( rhs, emode );
  2628.         printf("\etDUP;\en");
  2629.         if ( lhs->level == GLOBAL ) printf("\etSTORE(%s);\en", lhs->str);
  2630.         else printf("\etLSTORE(%d);\en", lhs->offset);
  2631.         break;
  2632. .cE
  2633. .cB
  2634.     case VAR :
  2635.         if ( emode == SIDE_EFFECTS ) break;
  2636.         if ( t->level == GLOBAL ) printf("\etPUSH(%s);\en", t->str);
  2637.         else printf("\etLPUSH(%d);\en", t->offset);
  2638.         break;
  2639. .cE
  2640. .cB
  2641.     case FUNC :
  2642.         gen( zzchild(t), VALUE );
  2643.         printf("\etCALL(%s);\en", t->str);
  2644.         break;
  2645. .cE
  2646. .cB
  2647.     case STRING :
  2648.         if ( emode == SIDE_EFFECTS ) break;
  2649.         printf("\etSPUSH(%s);\en", t->str);
  2650.         break;
  2651. .cE
  2652. .cB
  2653.     default :
  2654.         printf("Don't know how to handle: %s\en", zztokens[t->token]);
  2655.         break;
  2656.     }
  2657. }
  2658. .cE
  2659. .cB
  2660. EvalMode( tok )
  2661. int tok;
  2662. {
  2663.     if ( tok == Assign || tok == If || tok == While ||
  2664.          tok == Print || tok == Return ) return VALUE;
  2665.     else return SIDE_EFFECTS;
  2666. }
  2667. .cE
  2668. .NH 2
  2669. .iH Makefile for code generator
  2670. .PP
  2671. This makefile is roughly the same as before except that we need to
  2672. tell PCCTS to generate tree information and we need to link in the
  2673. code generator.
  2674. .cB
  2675. CFLAGS= -I../h
  2676. GRM=tut4
  2677. SRC=scan.c $(GRM).c err.c sym.c code.c
  2678. OBJ=scan.o $(GRM).o err.o sym.o code.o
  2679.  
  2680. tutorial: $(OBJ) $(SRC)
  2681.     cc -o $(GRM) $(OBJ)
  2682.  
  2683. $(GRM).c parser.dlg : $(GRM).g
  2684.     antlr -k 2 -gt $(GRM).g
  2685.  
  2686. scan.c : parser.dlg
  2687.     dlg -C2 parser.dlg scan.c
  2688. .cE
  2689. .pn 0
  2690. .bp
  2691. .PX
  2692.